algospot 보물섬 (문제ID: TREASURE) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/TREASURE

algospot.com :: TREASURE

하나의 다각형과 하나의 직사각형에 교집합인 교집합 다각형의 넓이를 구하는 문제이다.

먼저 다각형을 직사각형의 각변을 포함하는 직선으로 잘랐을때, 해당 직선 왼쪽에 있는 다각형의 꼭짓점들, 직선과 다각형의 교차점들을 모두 저장한다.

직사각형 각각의 변들에 따라 이 작업을 총 4번 반복하면 교집합 다각형의 꼭짓점만을 저장할 수 있다.

다각형의 점들 p0, p1, p2, ... p(n-1)이 반시계 순서대로 배열되면 벡터p(i)와 벡터p((i+1)%n)의 외적을 모두(i=0부터 n-1까지) 합해서 2로 나누면 다각형의 넓이를 구할 수 있다.

 

코드원본: https://github.com/sbl133/JongmanBook/blob/main/15.%20ComputationalGeometry/TREASURE.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1