단순 다각형이란, 볼록하거나 오목하기도 한 다각형이며, 다각형을 이루는 선이나 변이 서로 교차하지 않는 다각형을 뜻한다.

2차원 평면 좌표 상에서 임의의 한 점 (X,Y)와 단순 다각형을 이루는 꼭지점들이 주어졌을 때, (X,Y)가 다각형 안에 포함 되었는가 아닌가 혹은 다각형을 이루는 선분에 걸쳤는가를 판별하는 프로그램을 작성하라.

문제를 간단하게 하기 위해서 다각형을 이루는 모든 변은 좌표 축에 수직 혹은 수평하며, 다각형을 이루는 꼭지점의 좌표는 모두 정수 좌표이다. 입력된 다각형은 마지막으로 입력된 꼭지점을 제외하고, i번째로 입력된 꼭지점과 i+1번째로 입력된 꼭지점을 잇는 직선이 존재하며, 마지막 꼭지점은 맨 앞에 입력된 꼭지점과 이어져 있다.

#2395 upload 759회 done 162회 how_to_reg 136명

다각형 안의 점 timer 1초 memory 64MB

#2395

다각형 안의 점 1초 64MB