Problem E
Komdu til móts við okkur

Athugið: þetta er framhald af Komdu til móts við mig (meet me in the middle)

Það eru $n$ kjósendur. Tákna má draumastefnu $i$-ta kjósandans með punkti $(x_i,y_i)$ í planinu. Sérhver kjósandi hefur sveigjanleika $r_i$, sem táknar hversu langt stefna má vera frá draumastefnu hans þannig hann sé enn ánægður með stefnuna, frekar en óánægður. Slíkar stefnur segjum við að séu í samþykktarsvæði kjósandans. Nota má margar mismunandi firðir, en við höldum okkur við Evklíðska fjarlægð. Hver kjósandi er því táknaður með hringskífu.

Þessir kjósendur vilja koma til móts við hvern annann og skoðum við því sniðmengi samþykktarsvæða þeirra. Þetta svæði getur verið af ýmsum gerðum eftir því hvernig samþykktarsvæði kjósendanna eru. Sumir kjósendur samþykkja allt sem einhver annar kjósandi samþykkir, og skipta þá ekki máli við útreikning á sniðmengi. Þetta samsvarar því að skífa þeirra umlykur aðra skífu. Það á því að hunsa slíka kjósendur.

1. Einhverjar skífur skerast ekki, svo sniðmengið er tómt. Það er impossible (ómögulegt) að komast til móts við hvorn annann í þessu tilfelli.

2. Ein skífan er innan í öllum öðrum skífum, svo sú skífa gefur sniðmengi samþykktarsvæðanna.

3. Það er ófáfengilegt sniðmengi skífa. Í þessu tilfelli má lýsa sniðmenginu með skurðpunktum skífanna sem eru innan í öllum skífum og skilgreina þetta svæði.

Inntak

Fyrsta lína inntaksins inniheldur heiltölu $n$, fjölda kjósenda, þar sem $1\le n\le 500$. Svo fylgja $n$ línur. Lína $i$ inniheldur þrjár heiltölur $x_i,y_i,r_i$, sem tákna kjósanda $i$.

Öll hnit eru á bilinu $-{10}^6$ til ${10}^6$, endapunktar meðtaldir. Allir geislar (sveigjanleikar) eru á bilinu $1$ til $2\cdot {10}^6$, endapunktar meðtaldir. Þú mátt gera ráð fyrir að engir tveir kjósendur hafi nákvæmlega sömu skoðanir.

Úttak

Eftir því hvaða tilfelli fæst úr listanum að ofan, prentið

1. impossible (ómögulegt)

2. voter (kjósandi) og númer kjósandans sem skilgreinir þessa skífu sem er innan í öllum öðrum skífum.

3. compromise (málamiðlun) ásamt heiltöli $k$ sem gefur fjölda skurðpunkta sem skilgreina svæðið. Næst ættu að fylgja $k$ línur, hver með tveimur tölum $x,y$ og (að minnsta kosti) tveimur tölum sem gefa númer kjósandanna sem skilgreina þann skurðpunkt. Prenta skal þessi núemr í vaxandi röð. Raða skal skurðpunktunum í orðabókaröð eftir kjósendunum sem skilgreina þá.

Svar þitt telst rétt ef hlutfallsleg skekkja þess frá réttu svari er mest ${10}^{-6}$.

1
0 0 10

voter 1

3
0 0 1
3 0 1
50 50 1000

impossible

3
75 83 62
6 62 78
45 89 100

compromise 2
72.3890578633145208 21.0550003538713363 1 2
38.3225915023140836 132.9876755400156302 1 2

4
19 86 68
34 46 54
87 19 68
94 62 65

compromise 4
84.0646935600472246 66.2367600850177092 1 2
42.5915250314730091 22.2235157233531535 1 4
71.2032546416990518 85.1397220744462869 2 3
29.3682060413785008 55.0912222723337324 3 4

5
-4 -7 90
40 30 100
3 4 54
-6 10 70
0 -20 80

voter 3

5
0 2 3
0 2 2
2 0 2
0 -2 2
-2 0 2

compromise 1
0.0000000000000000 0.0000000000000000 2 3 4 5

5
-16 63 65
-63 16 65
8 -57 65
55 -10 65
-4 3 5

compromise 6
0.0000000000000001 0.0000000000000000 1 2 5
-6.5384615384615385 -1.3076923076923077 1 5
0.8904109589041096 4.0410958904109588 2 5
-8.0000000000000000 6.0000000000000000 3 4 5
-1.4615384615384615 7.3076923076923077 3 5
-8.8904109589041096 1.9589041095890412 4 5