0935 - Punct In Poligon Simplu: Diferență între versiuni
AjM (discuție | contribuții) |
AjM (discuție | contribuții) |
||
Linia 11: | Linia 11: | ||
În primele două teste poligonul este convex. | În primele două teste poligonul este convex. | ||
== Exemplu == | == Exemplu == | ||
punctinpoligonsimplu.in | <nowiki>;</nowiki> punctinpoligonsimplu.in | ||
8 9 | 8 9 | ||
Linia 49: | Linia 49: | ||
20 0 | 20 0 | ||
punctinpoligonsimplu.out | <nowiki>;</nowiki> punctinpoligonsimplu.out | ||
DA | DA |
Versiunea de la data 3 iunie 2024 14:58
Cerinţa
Se dau coordonatele în plan pentru n puncte care determină un poligon. Se mai dau coordonatele altor m puncte. Să se verifice, pentru fiecare dintre cele m puncte, dacă se găsește sau nu în interiorul (sau pe marginea) poligonului.
Date de intrare
Fișierul de intrare punctinpoligonsimplu.in conține pe prima linie două numere separate prin spațiu: n și m, reprezentând respectiv, numărul de vârfuri ale poligonului și numărul de puncte de testat. 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 vârf al poligonului. Acestea sunt date între-un sens de parcurgere a laturilor poligonului. Pe următoarele m linii se găsesc câte două numere separate printr-un spațiu, reprezentând abscisa respectiv ordonata câte unui punct care trebuie testat.
Date de ieșire
Fișierul de ieșire punctinpoligonsimplu.out va conține m linii și pe fiecare dintre ele sa află mesajul DA sau NU după cum punctul corespunzător este sau nu în interiorul
Restricţii şi precizări
1 ≤ n , m ≤ 100 Numerele din fișierul de intrare sunt întregi cuprinse între -1001 și 1001. Poligonul nu este neapărat convex dar nu se autointersectează. În primele două teste poligonul este convex.
Exemplu
; punctinpoligonsimplu.in
8 9
-4 -1
-3 2
-1 3
2 3
4 1
4 -2
1 -4
-2 -4
0 0
-3 -2
3 -2
-1 2
2 2
-4 0
-2 3
0 -20
20 0
; punctinpoligonsimplu.out
DA
DA
DA
DA
DA
NU
NU
NU
NU
Rezolvare
def is_point_in_polygon(n, vertices, point):
x, y = point
inside = False
p1x, p1y = vertices[0]
for i in range(n + 1):
p2x, p2y = vertices[i % n]
if y > min(p1y, p2y):
if y <= max(p1y, p2y):
if x <= max(p1x, p2x):
if p1y != p2y:
xinters = (y - p1y) * (p2x - p1x) / (p2y - p1y) + p1x
if p1x == p2x or x <= xinters:
inside = not inside
p1x, p1y = p2x, p2y
return inside
def read_input_file(filename):
with open(filename, 'r') as file:
data = file.readlines()
n, m = map(int, data[0].strip().split())
vertices = [tuple(map(int, line.strip().split())) for line in data[1:n+1]]
points = [tuple(map(int, line.strip().split())) for line in data[n+1:]]
return n, m, vertices, points
def write_output_file(filename, results):
with open(filename, 'w') as file:
for result in results:
file.write(result + "\n")
def main():
n, m, vertices, points = read_input_file('punctinpoligonsimplu.in')
results = []
for point in points:
if is_point_in_polygon(n, vertices, point):
results.append('DA')
else:
results.append('NU')
write_output_file('punctinpoligonsimplu.out', results)
if __name__ == "__main__":
main()