0935 - Punct In Poligon Simplu

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

<syntaxhighlight lang="python" line> 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()

</syntaxhighlight>