루미 알고리즘

#1279플래티넘Fabriksrobot

PO 2005 결선코딩스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

(그림은 원문 저장소에서 볼 수 있습니다)

Figur 1: Förklaring till exemplet. Det kritiska avståndet är det mellan pelare 1 och 2 i indata. Avståndet mellan deras centrumpunkter är cirka 405.123, och det verkliga avståndet däremellan är 405.12 - 110 - 30 = 265.12, vilket gör att den maximala radien på roboten är 265.12/2 = 132.56.

På ett stort fabriksgolv (storlek 1000 × 1000 meter) finns ett antal cirkulära pelare med varierande radie. Pelarna tangerar inte varandra eller väggarna. Företaget, som äger fabriken, planerar att köpa in en vaktrobot som ska röra sig i lokalen. I lokalens fyra hörn finns maskiner placerade till vilka roboten måste kunna ta sig genom att sick-sacka fram mellan pelare och väggar. De vaktrobotar som finns på marknaden är alla, liksom pelarna, helt cirkulära. Innan företaget köper in en robot vill de dock veta vad den maximala radien på roboten får vara för att deras krav fortfarande ska kunna uppfyllas.

Ingen del av roboten får sticka ut utanför lokalen. Om roboten har radien r så ska den kunna ta sig till punkterna (r, r), (1000 - r, r), (r, 1000 - r) respektive (1000 - r, 1000 - r) och därifrån betjäna de fyra maskinerna. Maskinerna utgör aldrig något hinder för robotens framfart.

Indata

Den första raden innehåller ett heltal n (1 ≤ n ≤ 50), antalet pelare i lokalen.

Därefter följer n rader som vardera innehåller 3 heltal, x, y och r. Dessa tal beskriver koordinaterna för en pelares centrum samt dess radie.

Utdata

Skriv ut ett flyttal: robotens maximala radie. Svaret accepteras om skillnaden mellan det och domarens svar är mindre än 0.01.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängGränser
120n = 1
280Inga ytterligare begränsningar.

예제

예제 1

입력
3
165 520 110
560 430 30
590 115 75
출력
132.56

출처 표기

출처: Programmeringsolympiaden 2005년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.