RaulOtet: Pagină nouă: 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...

2024-07-25T12:38:29Z

Pagină nouă: 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...

New page

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>

0750 - S Min - Revision history