문제
컨벡스 헐로 이뤄진 2차원 평면 좌표의 집합 S에 대해 다음과 같은 연산을 수행하는 프로그램을 작성하라.
1. 추가 : 점 (x,y)를 S 추가한다. 이 경우 S가 변할 수 도 있으며, 그대로 유지될 수 있다. 2. 판별 : 점 (x,y)가 S가 이루는 컨벡스 헐 안에 존재하는가를 판단한다. 만약 선분에 존재할 경우에도 컨벡스 헐 안에 위치해 있다고 간주한다.
입력
입력의 첫번쨰 줄에는 연산의 개수 Q가 입력된다. Q는 4이상 100,000이하의 정수이다. 그 다음에 Q개의 연산이 주어지며, 정수 t, x, y의 형태로 입력된다. t는 연산의 형태를 뜻하며 1의 경우 위에 언급된 추가 연산, 2의 경우에는 판별 연산을 뜻한다. x와 y는 -1,000,000이상 1,000,000이하의 정수이다.
처음에 총 3개의 1번 연산이 주어지고, 3각형의 형태로 주어진다. 적어도 하나의 2번 연산이 입력된다. 1번 연산에 대해 동일한 점이 여럿 들어오는 경우는 존재하지 않는다.
출력
입력에 대해 2번 연산에 대해 입력된 점이 컨벡스 헐 안에 존재할 경우 "YES"를 그렇지 않을 경우 "NO"를 출력한다.
예제
8
1 0 0
1 2 0
1 2 2
2 1 0
1 0 2
2 1 1
2 2 1
2 20 -1
YES
YES
YES
NO
로그인해야 코드를 작성할 수 있어요.