View source for 0750 - S Min

Ana are un joc nou. Pe o tablă pătrată este trasat un grid format din celule pătratice de dimensiune <code>1</code>. În oricare dintre colţurile oricărei celule, Ana poate înfige câte un beţişor perpendicular pe tablă. După ce a plasat <code>n</code> beţişoare, Ana ia dintr-o cutie (cu un număr suficient de mare de corzi elastice circulare) câte o coardă cu care înconjoară trei sau mai multe beţişoare. Fiecare coardă este bine întinsă şi formează pe tablă un contur poligonal. 

În figura alăturată este folosită o coardă ce formează un contur poligonal cu <code>4</code> laturi cu care sunt înconjurate <code>5</code> dintre cele <code>8</code> beţişoare de pe tablă.

Jocul se încheie când au fost plasate atâtea coarde încât toate beţişoarele de pe tablă să se afle pe marginea sau în interiorul a cel puţin unul dintre contururile poligonale formate. Scopul jocului este ca amplasarea corzilor să fie făcută convenabil astfel încât totalul ariilor contururilor poligonale formate să fie minim.

= Cerința =
Cunoscând coordonatele celor <code>n</code> beţişoare <code>(x[1], y[1])</code>, <code>(x[2], y[2])</code>, …, <code>(x[n], y[n])</code> măsurate faţă de unul dintre colţurile gridului, Ana doreşte să găsească suma minimă a ariilor poligonale obţinute prin amplasarea convenabilă a coardelor, astfel încât fiecare beţişor să se găsească în interiorul sau pe conturul a cel puţin un astfel de poligon.

= Date de intrare =
Fișierul de intrare <code>smin.in</code> conține pe prima linie numărul natural <code>n</code>. Pe fiecare dintre următoarele <code>n</code> linii, se află câte două numere naturale: <code>x y</code>.

= Date de ieșire =
Fișierul de ieșire <code>smin.out</code> va conține pe prima linie numărul real <code>s</code>, reprezentând suma minimă a ariilor poligoanelor convexe care acoperă toate punctele date.

= Restricții și precizări =

* <code>3 ≤ n ≤ 17</code>
* <code>0 ≤ x, y ≤ 100</code>
* Datele de intrare nu vor conţine trei beţişoare plasate în puncte coliniare din planul tablei.
* Suma cerută se obţine însumând ariile tuturor poligoanelor, indiferent dacă unele poligoane se suprapun sau nu.
* Modulul diferenţei dintre valoarea reală a lui <code>s</code> şi cea afişată este mai mic decât <code>0.001</code>.

= Exemplu: =
<code>smin.in</code>
 4
 0 2
 0 4
 4 4
 4 2
<code>smin.out</code>
 8.000

= Explicație =
Aria minimă  este dreptunghiul din prima figură, cu cele patru beţişoare în vârfuri. Se foloseşte o singură coardă elastică.<syntaxhighlight lang="python" line="1">
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
    elif val > 0:
        return 1
    else:
        return 2

def convex_hull(points):
    n = len(points)
    if n < 3:
        return points

    l = min(range(n), key=lambda i: (points[i][0], points[i][1]))
    hull = []

    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

def polygon_area(points):
    n = len(points)
    area = 0.0
    for i in range(n):
        j = (i + 1) % n
        area += points[i][0] * points[j][1]
        area -= points[j][0] * points[i][1]
    return abs(area) / 2.0

def remaining_points(points, hull):
    hull_set = set(hull)
    return [p for p in points if p not in hull_set]

def minimum_total_area(points):
    total_area = 0.0
    while points:
        hull = convex_hull(points)
        total_area += polygon_area(hull)
        points = remaining_points(points, hull)
    return total_area

# Citirea datelor de intrare
n = int(input("Introduceți numărul de bețișoare: "))
points = []

for _ in range(n):
    x, y = map(int, input().split())
    points.append((x, y))

# Calcularea ariei minime totale
result = minimum_total_area(points)
print(f"Suma minimă a ariilor contururilor poligonale este: {result}")
</syntaxhighlight>