0935 - Punct In Poligon Simplu - Revision history

AjM: /* Exemplu */

2024-06-03T16:13:22Z

Exemplu

@@ Line 11: / Line 11: @@
 În primele două teste poligonul este convex.
 == Exemplu ==
-<nowiki>;</nowiki> punctinpoligonsimplu.in
+; punctinpoligonsimplu.in
-9
+<br>
 == Rezolvare ==
 <syntaxhighlight lang="python" line>

AjM: /* Exemplu */

2024-06-03T16:11:32Z

Exemplu

← Older revision		Revision as of 16:11, 3 June 2024
Line 11:		Line 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
Line 49:		Line 49:
	20 0		20 0

	punctinpoligonsimplu.out		<nowiki>;</nowiki> punctinpoligonsimplu.out

	DA		DA
Line 68:		Line 68:

	NU		NU

			<nowiki><br></nowiki>
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>

AjM: /* Exemplu */

2024-06-03T14:58:57Z

Exemplu

← Older revision		Revision as of 14:58, 3 June 2024
Line 11:		Line 11:
	În primele două teste poligonul este convex.		În primele două teste poligonul este convex.
	== Exemplu ==		== Exemplu ==
	~~<nowiki>;</nowiki>~~ punctinpoligonsimplu.in		punctinpoligonsimplu.in

	8 9		8 9
Line 49:		Line 49:
	20 0		20 0

	~~<nowiki>;</nowiki>~~ punctinpoligonsimplu.out		punctinpoligonsimplu.out

	DA		DA

AjM: /* Exemplu */

2024-06-03T14:58:46Z

Exemplu

← Older revision		Revision as of 14:58, 3 June 2024
Line 11:		Line 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
Line 49:		Line 49:
	20 0		20 0

	punctinpoligonsimplu.out		<nowiki>;</nowiki> punctinpoligonsimplu.out

	DA		DA

AjM: /* Exemplu */

2024-06-03T14:46:15Z

Exemplu

← Older revision		Revision as of 14:46, 3 June 2024
Line 14:		Line 14:

	8 9		8 9

	-4 -1		-4 -1

	-3 2		-3 2

	-1 3		-1 3

	2 3		2 3

	4 1		4 1

	4 -2		4 -2

	1 -4		1 -4

	-2 -4		-2 -4

	0 0		0 0

	-3 -2		-3 -2

	3 -2		3 -2

	-1 2		-1 2

	2 2		2 2

	-4 0		-4 0

	-2 3		-2 3

	0 -20		0 -20

	20 0		20 0

	punctinpoligonsimplu.out		punctinpoligonsimplu.out

	DA		DA

	DA		DA

	DA		DA

	DA		DA

	DA		DA

	NU		NU

	NU		NU

	NU		NU

	NU		NU
	== Rezolvare ==		== Rezolvare ==

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

2024-06-03T14:45:19Z

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

New page

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