공장에서 작업을 하는 로봇은 고정 축 F, 한 개의 관절 A, 두개의 뼈대 B, C와 손 D로 구성되어 있다.

그림 1과 같이 고정축 F는 공장 내부의 한 점에 고정되어 있고,

뼈대 B는 고정축 F와 관절 A사이를 연결하고,

다른 뼈대 C는 관절 A와 손 D사이를 연결한다.

그림 1

단, 뼈대 B와 C는 그림 2와 같이 다음 조건을 만족하면서 움직일 수 있다.

(1) 뼈대 B는 고정축에서 왼쪽 또는 오른쪽 수평방향으로 나오거나,

고정 축에서 위쪽 또는 아래쪽 수직방향으로 나올 수 있다. (2) 뼈대 C는 관절 A에서 뼈대 B와 항상 수직을 이루면서 나온다. (3) 뼈대 B와 C는 길이를 0에서 얼마든지 자유자재로 연장할 수 있다.

그림 2

로봇의 고정축이 위치한 공장은 그림 3과 같이 수평 방향과 수직 방향의 벽들이

번갈아 가면서 연결되어 있는 하나의 다각형으로 구성되어 있다.

따라서, 이 공장의 내부에는 벽들이 존재하지 않는다.

이 공장 내부의 어떤 위치에 로봇의 고정축 F를 고정시켰을 때,

위의 세 가지 조건들을 만족하면서 뼈대 B와 C의 위치와 길이를 조절하더라도

로봇의 손 D가 미치지 못하는 공장 내부의 지점이 있을 수 있다.

그림 3

그림 3의 예에서 로봇의 고정축이 P지점에 고정되어 있으면 공장 내부의 모든 위치에 로봇 손 D가 접근할 수 있지만,

Q지점에 고정되어 있으면 로봇 손 D가 도달할 수 없는 지점(빗금 친 부분)이 존재한다.

공장의 경계를 나타내는 다각형의 꼭지점과 로봇의 고정축의 위치가 주어질 때,

공장의 내부에 로봇 손이 도달하지 못하는 부분이 있는 지를 검사하는 프로그램을 작성하시오.

단, 고정축은 공장의 내부에 존재하며, 공장의 내부는 경계선을 포함하지 않는다.

뼈대 B, C는 공장의 경계선을 따라 움직일 수 있고,

고정축, 관절과 손은 점으로, 뼈대는 두께가 없는 선분으로 가정한다.

부분 점수는 없다.

로봇 timer 1s memory 128MB

로봇 1s 128MB