Editing 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

<br>


== 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>