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

2024-06-03T14:46:28Z

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

New page

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

0936 - Infasuratoare Convexa - Revision history