Almost Clear
시간 제한1초메모리 제한128 MB
서로 겹치지 않는 두 볼록 다각형 A, B와 두 다각형 밖의 점 C가 주어질 때, C에서 볼 때 B가 A를 전혀 가리지 않는지, 일부만 가리는지, 전부 가리는지 판정한다.
문제
한 박물관은 값비싼 전시품을 여러 개 전시하며, 모든 전시품을 감시할 수 있도록 감시 카메라를 설치한다. 당신의 임무는 카메라 하나와 장애물 하나에 대해 가림 정도를 판정하는 것이다.
2차원 평면 위에 볼록 다각형 (전시품), 볼록 다각형 (다른 물체), 그리고 점 (카메라)가 주어진다. 카메라를 점 에 두었을 때 다각형 가 다각형 를 얼마나 가리는지 판정하라.
가정:
- 모든 좌표는 2차원 평면 위에 있다.
- 다각형 와 는 모두 볼록하다.
- 카메라의 시야는 무한하다(아무리 멀리 있어도 볼 수 있다).
- 카메라는 360° 자유롭게 회전할 수 있다.
- 카메라는 점 에서 움직일 수 없다.
- 모든 배치는 유효하다. 두 다각형은 서로 교차하지 않으며, 카메라는 어떤 다각형의 내부에도 있지 않다.
다각형 의 한 점 는, 에서 로 향하는 선분이 다각형 를 지날 때 "가려진다". 가 가려지는 정도에 따라 가 완전히 보이는지, 일부만 가려지는지, 완전히 가려지는지를 판정해야 한다.
입력
첫 번째 줄에 테스트 케이스의 수 ()가 주어진다.
각 테스트 케이스는 세 줄로 이루어진다.
- 첫 번째 줄은 다각형 를 나타낸다. 정점의 개수 ()에 이어, 정점을 반시계 방향으로 나열한 개의 좌표쌍 가 주어진다.
- 두 번째 줄은 같은 형식으로 다각형 를 나타낸다.
- 세 번째 줄에는 카메라 의 좌표와 좌표, 두 정수가 주어진다.
모든 좌표는 음이 아니며 미만이다.
출력
각 테스트 케이스마다 정확히 한 줄을 출력한다.
- 다각형 가 다각형 에 전혀 가려지지 않으면
CLEAR, - 다각형 가 다각형 에 일부만 가려지면
ALMOST CLEAR, - 다각형 가 다각형 에 완전히 가려지면
NO VISION을 출력한다.