====== انتقال تسموی ====== مشخصات $n$‌چرخ دایره‌ای شکل داده شده است. می‌دانیم دقیقا در حالی‌که دو چرخ با هم هیچ نقطه‌ی مشترکی نداشته باشند، می‌توان تسمه‌ای به دورشان انداخت و آن‌ها را به هم وصل کرد. می‌دانیم در بازار فقط تسمه‌هایی با طول صحیح پیدا می‌شود. تسمه نمی‌تواند خودش را قطع کند و اگر دو چرخ با تسمه‌ای به طول $L$ به هم وصل شوند با تسمه‌های بلند‌تر هم به هم وصل می‌شوند. می‌خواهیم طوری چرخ‌ها را به هم وصل کنیم که همه‌ی چرخ‌ها به هم وصل شوند و طول بزرگ‌ترین تسمه‌ای که خریداری می‌شود کمینه باشد. ===== ورودی ===== در خط اول فایل ورودی عدد $n$‌($1 \leq n \leq 10^4$) آمده و در $n$ خط بعد در هر خط سه عدد $x_i$ و $y_i$ و $r_i$ آمده. که $(x_i,y_i)$ مختصات مرکز چرخ و $r_i$ شعاع چرخ $i$ است. ===== خروجی ===== در فایل خروجی کمینه‌ی مقدار طول بزرگ‌ترین تسمه‌ای که خریداری می‌شود را بنویسید. فرض کنید مسئله همیشه جواب دارد ===== محدودیت‌ها ===== * محدودیت زمان: ۳۰ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |3 \\ 0 0 1 \\ 0 0 13 \\ 15 0 1 |85| <پاسخ> * [[سوال ۷|سوال بعد]] * [[سوال ۵|سوال قبل]]