Arbitraža

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 128 MB
Avtor:
  • Tomaž Hočevar
  • UPM 2013

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Po več letih državljanske vojne sta sprti strani končno prišli do sporazuma. Ozemeljsko vprašanje bosta rešili z arbitražo. Država ima obliko enostavnega večkotnika (stranice se med seboj ne sekajo), arbitražni sporazum pa določa, da bo arbiter s premico razdelil državo na dva dela. Pri tem lahko na vsaki strani premice nastane več območij, saj država ni nujno konveksna. Vsa območja na isti strani premice bodo pripadala enim, ostala pa drugim.

Orožarska industrija je poskrbela, da v sporazumu ni določeno, kdo dobi katero stran delitvene premice in si s tem zagotovila nemoteno poslovanje še naslednjih nekaj let. V tej nalogi pa nas zanima samo, kako poštena je delitev arbitra. Kakšen delež površine države bo prejela bolj srečna oz. vplivna stran?

Vhodni podatki

V prvi vrstici se nahaja število oglišč večkotnika N. V naslednjih N vrsticah si sledijo pari celih števil X_i, Y_i, ki določajo koordinate oglišč, kot si sledijo v večkotniku. Vsako oglišče je povezano z naslednjim, zadnje pa s prvim. Zadnja vrstica vsebuje štiri cela števila: X_a, Y_a, X_b in Y_b; arbitražna premica poteka skozi točki (X_a,Y_a), (X_b,Y_b).

Primer testnih podatkov je ilustriran na spodnji sliki.

Testni primer

Omejitve vhodnih podatkov

  • 3 \leq N \leq 10^5
  • |X_i|, |Y_i| \leq 10^5

Izhodni podatki

Izpiši delež površine države, ki ga prejme bolj uspešna stran na arbitraži. Iščemo torej razmerje med večjim delom in celotno površino. Rešitev bo pravilna, če se bo od uradne rešitve razlikovala za največ 10^{-9}.

Primer

Vhod

11
1 3
2 0
4 3
6 0
7 3
7 4
6 1
4 4
4 4
2 1
1 4
0 2 3 2

Izhod

0.5

Komentar

Delitvena črta razdeli večkotnik po površini točno na polovico. V tem primeru se je arbiter izkazal za poštenega.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task