[알고리즘문제] 볼록 다각형의 교차 영역 Question. 평면상에 볼록 다각형 P가 주어져 있다. 다각형 내에 있는 임의의 두 점을 잇는 선분이 다각형 내에 완전히 속하는 다각형을 볼록 다각형이라고 한다. 그리고 변이 모두 x축이나 y축에 평행인 직사각형 Q가 있다. 문제는 P와 Q의 교차영역을 구하는 프로그램을 작성하는 것이다. 예를 들면 아래 그림과 같이P와 Q가 주어질 수 있다. 그림에서 P는 각형이며 Q는 점선으로 표시되어 있다. 두 볼록 다각형의 교차 영역은 볼록 다각형이 됨에 주의한다. 다각형을 나타낼 때는 임의의 한 꼭지점에서 시작하여 다각형을 반시계 방향으로 따라갈 때 만나는 꼭지점의 열(sequence)로 나타낼 수 있다. 꼭지점은 x,y-좌표값으로 나타낸다. 그리고 4각형 Q를 나타내기 위해서는 왼쪽 아래 꼭지점과 오른쪽 위.. 더보기 이전 1 ··· 177 178 179 180 181 182 183 ··· 385 다음
