0936 - Infasuratoare Convexa

Cerinţa

Se dau puncte distincte în plan. Să se determine un poligon de arie maximă care are vârfuri dintre punctele date.

Date de intrare

Fișierul de intrare infasuratoareconvexa.in conține pe prima linie un număr n, reprezentând numărul de puncte. Pe următoarele n linii se găsesc câte două numere separate printr-un spațiu, reprezentând abscisa respectiv ordonata câte unui punct.

Date de ieșire

Fișierul de ieșire infasuratoareconvexa.out va conține pe prima linie un număr k, reprezentând numărul de vârfuri ale poligonului determinat. Pe următoarele k linii se găsesc câte două numere separate printr-un spațiu, reprezentând respectiv abscisa și ordonata câte unui punct.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• Numerele din fișierul de intrare sunt întregi cuprinse între -1001 și 1001.
• Primul punct care se va afișa va fi cel cu ordonata minimă, iar în caz de egalitate cel cu abscisa minimă.
• Punctele se vor afișa în sens trigonometric al parcurgerii lor pe înfășurătoare.
• Se cere soluția cu număr maxim de puncte (pot fi puncte coliniare pe înfășurătoare).

Exemplul 1

infasuratoareconvexa.in

5 1 1 0 0 0 2 2 2 2 0

infasuratoareconvexa.out

4 0 0 2 0 2 2 0 2

Rezolvare

<syntaxhighlight lang="python" line> import math

def orientation(p, q, r):

   val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
   if val == 0:
       return 0  
   return 1 if val > 0 else 2  

def convex_hull(points):

   n = len(points)
   if n < 3:
       return []

   hull = []

   l = 0
   for i in range(1, n):
       if points[i][1] < points[l][1] or (points[i][1] == points[l][1] and points[i][0] < points[l][0]):
           l = i

   p = l
   while True:
       hull.append(points[p])
       q = (p + 1) % n
       for i in range(n):
           if orientation(points[p], points[i], points[q]) == 2:
               q = i
       p = q
       if p == l:
           break

   return hull

with open("infasuratoareconvexa.in", "r") as fin:

   n = int(fin.readline().strip())
   points = [list(map(int, fin.readline().split())) for _ in range(n)]

convex_points = convex_hull(points)

convex_points.sort(key=lambda x: (x[1], x[0]))

with open("infasuratoareconvexa.out", "w") as fout:

   fout.write(str(len(convex_points)) + "\n")
   for point in convex_points:
       fout.write(" ".join(map(str, point)) + "\n")

</syntaxhighlight>