0750 - S Min

Ana are un joc nou. Pe o tablă pătrată este trasat un grid format din celule pătratice de dimensiune 1. În oricare dintre colţurile oricărei celule, Ana poate înfige câte un beţişor perpendicular pe tablă. După ce a plasat n 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 4 laturi cu care sunt înconjurate 5 dintre cele 8 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 n beţişoare (x[1], y[1]), (x[2], y[2]), …, (x[n], y[n]) 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 smin.in conține pe prima linie numărul natural n. Pe fiecare dintre următoarele n linii, se află câte două numere naturale: x y.

Date de ieșire

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

Restricții și precizări

• 3 ≤ n ≤ 17
• 0 ≤ x, y ≤ 100
• 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 s şi cea afişată este mai mic decât 0.001.

Exemplu:

smin.in

4
0 2
0 4
4 4
4 2

smin.out

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

1. 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))

1. Calcularea ariei minime totale

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