2060 - Episodul 2

Enunt

După ce a luat aur la ONI2017, Roby băiatul de aur a decis să ajute la construcția tării Zoomba. Zoli astfel i-a cerut să se ocupe de construirea unui acoperiș ce va acoperi toată țara. Acesta va fi alcătuit din grinzi ce se vor sprijini pe puncte în sistemul cartezian. O grindă va uni două puncte. Acoperișul trebuie construit în așa fel încât, privit de sus, orice unghi format de către două grinzi consecutive să fie ≥ 180 (în cazul în care plouă, nu se dorește ca acesta să țina apa) și să acopere toate punctele de sprijin. Din când în când, Zoli este interesat de aria poligonului format din totalitatea punctelor ce se află sub acoperiș și deasupra axei OX. Astfel se disting următoarele evenimente:

1 x y: Se adaugă punctul de coordonate întregi (x, y) în plan. De acum încolo, se vor putea așeza grinzi pe acesta. 2: Zoli întreabă care este aria poligonului descris mai sus.

Cerinţa

Scrieți un program care procesează M evenimente de tipurile precizate mai sus, și afișează în fișierul de ieșire rezultatele evenimentelor de tipul 2.

Date de intrare

Fișierul de intrare episodul2.in conține pe prima linie numărul M, iar pe fiecare linie din cele M, se va afla câte un eveniment, cu formatul specificat mai sus.

Date de ieșire

Fișierul de ieșire episodul2.out va conține pe fiecare linie câte un număr, reprezentând răspunsurile operațiilor de tip 2, în ordinea în care acestea apar în fișierul de intrare.

Restricţii şi precizări

1 ≤ M ≤ 200.000
Pentru operațiile de tip 1, 1 ≤ x, y ≤ 1.000.000, iar punctele se dau în ordine lexicografică.

Exemplul 1

episodul2.in

9 1 2 6 1 4 6 2 1 5 3 2 1 5 5 2 1 7 4 2

episodul2.out

12 16.5 17.5 27

Rezolvare

<syntaxhighlight lang="python" line> def cross(o, a, b):

   return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def convex_hull(points):

   points = sorted(points)
   lower = []
   for p in points:
       while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
           lower.pop()
       lower.append(p)
   upper = []
   for p in reversed(points):
       while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
           upper.pop()
       upper.append(p)
   return lower[:-1] + upper[:-1]

def polygon_area(vertices):

   n = len(vertices)
   area = 0
   for i in range(n):
       x1, y1 = vertices[i]
       x2, y2 = vertices[(i + 1) % n]
       area += x1 * y2 - y1 * x2
   return abs(area) / 2

def process_events(events):

   points = []
   results = []
   
   for event in events:
       if event[0] == 1:
           _, x, y = event
           points.append((x, y))
       elif event[0] == 2:
           filtered_points = [(x, y) for x, y in points if y >= 0]
           if len(filtered_points) < 3:
               results.append(0.0)
           else:
               hull = convex_hull(filtered_points)
               area = polygon_area(hull)
               results.append(area)
   
   return results

def main():

   import sys
   input = sys.stdin.read
   data = input().split()
   
   M = int(data[0])
   events = []
   
   idx = 1
   for _ in range(M):
       event_type = int(data[idx])
       if event_type == 1:
           x = int(data[idx + 1])
           y = int(data[idx + 2])
           events.append((1, x, y))
           idx += 3
       elif event_type == 2:
           events.append((2,))
           idx += 1
   
   results = process_events(events)
   
   with open("episodul2.out", "w") as f:
       for result in results:
           f.write(f"{result:.6f}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>