Posestvo

Osnovne informacije

Omejitve
  • Čas: 1 s
  • Spomin: 128 MB
Avtor:
  • Niko Lukač
  • UPM 2013

Pošlji rešitev



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

Kavboj Jim se je po dolgih letih ropanja odločil ustaliti in si s svojimi prihranki kupiti posestvo. Jim je svoje posestvo zakoličil skupaj z mesnim uradnikom, s katerim sta opravila obhod. Sicer je res, da je Jim svoje posestvo zakoličil bolj "po kavbojsko", je pa to zagotovo konveksne oblike. V času nastajanja prvih mest na divjem zahodu so občinske uprave vodile zelo preprost zemljiški kataster razdeljen na parcele kvadratne oblike. Ker Jim ni zakoličil pravokotnega posestva, morajo mestni uradniki sami ugotoviti katere parcele želi Jim kupiti, pri čemer Jimu pripišejo vsako parcelo znotraj zakoličenega območja, vključno s tistimi skozi katere gre ravna povezava med dvema količkoma.

alt text

Naloga

Pomagajte mestnim uradnikom pri njihovem delu in izdelajte program, ki določi Jimovo posestvo. Parcela pripada posestvu, če se meja nahaja znotraj dane parcele, kjer je upoštevano odstopanje do 10^{-5} enot – meja lahko za malenkost zgreši parcelo ali se zgolj dotika vogala, pa jo kljub temu pripišemo Jimu.

Vhodni podatki

V prvi vrstici je zapisano število količkov N. Nato v N vrsticah sledijo zapisi količkov, kjer sta v vsaki vrstici zapisani koordinati X_i in Y_i (ločeni s presledkom) za posamezen količek.

Omejitve vhodnih podatkov

  • 2 < N < 30
  • 0 < X_i, Y_i < 2^{64}

Izhodni podatki

Izpišite eno samo število – ploščino M (število parcel) posestva.

Omejitve izhodnih podatkov

  • 3 \leq M \leq 1000

Primeri

Vhod

4
10 10
13 10
13 13
10 13

Izhod

16

Vhod

3
116 112
118 115
114 115

Izhod

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