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

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()