Vizualizare sursă pentru „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

<br>

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