새로 심은 나무
시간 제한0.2초메모리 제한1024 MB
점 A와 새 나무가 주어질 때, 삼각형 ABC가 반시계 방향이고 새 나무를 내부에 포함하며 다른 옛 나무를 포함하지 않는 가장 작은 순서쌍 (B, C)를 찾는다.
문제
도시 공원에 나무를 새로 한 그루 심었고, 정원사는 이 나무를 보호하려고 한다. 정원사는 오래된 나무 세 그루를 골라 그 둘레에 띠를 두르고, 띠가 이루는 삼각형 안쪽이 보호 구역이 된다. 새 나무는 이 삼각형의 내부에 있어야 하고, 다른 나무는 삼각형 내부에도 경계 위에도 있으면 안 된다.
정원사는 오래된 나무 중 번호가 인 나무를 이미 골라 두었다. 나머지 두 그루를 찾아라.
오래된 나무에는 번부터 번까지 번호가 붙어 있다. 다음 조건을 모두 만족하는 번호 쌍 가 올바른 답이다.
- 와 는 서로 다르고, 둘 다 와도 다르다.
- 오래된 나무 , , 를 이 순서로 이으면 반시계 방향이다. 즉 세 점이 한 직선 위에 있지 않다.
- 새 나무가 삼각형 의 내부에 있다. 변 위에 있으면 안 된다.
- , , 가 아닌 오래된 나무는 삼각형 의 내부에도, 세 변 위에도 없다.
입력
첫째 줄에 오래된 나무의 수 과 정원사가 이미 고른 나무의 번호 가 주어진다 (, ).
둘째 줄에 새 나무의 좌표 와 가 주어진다.
다음 개 줄에는 오래된 나무의 좌표 와 가 번호 순서대로 한 줄에 한 그루씩 주어진다 (). 개의 점은 모두 서로 다르다.
출력
, , 순서로 올바른 보호 구역을 이루는 와 를 공백 하나로 구분해 한 줄에 출력한다.
올바른 쌍이 여러 개면 가장 작은 것을 출력한다. 먼저 를 비교하고, 가 같을 때만 를 비교한다. 올바른 쌍이 하나도 없으면 0 0을 출력한다.