아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

새로 심은 나무

시간 제한0.2초메모리 제한1024 MB

요약
점 A와 새 나무가 주어질 때, 삼각형 ABC가 반시계 방향이고 새 나무를 내부에 포함하며 다른 옛 나무를 포함하지 않는 가장 작은 순서쌍 (B, C)를 찾는다.
난이도

보통10점 중 6점

유형
기하, 완전 탐색
정답자
아직 제출이 없습니다

문제

도시 공원에 나무를 새로 한 그루 심었고, 정원사는 이 나무를 보호하려고 한다. 정원사는 오래된 나무 세 그루를 골라 그 둘레에 띠를 두르고, 띠가 이루는 삼각형 안쪽이 보호 구역이 된다. 새 나무는 이 삼각형의 내부에 있어야 하고, 다른 나무는 삼각형 내부에도 경계 위에도 있으면 안 된다.

정원사는 오래된 나무 중 번호가 AA인 나무를 이미 골라 두었다. 나머지 두 그루를 찾아라.

오래된 나무에는 11번부터 NN번까지 번호가 붙어 있다. 다음 조건을 모두 만족하는 번호 쌍 (B,C)(B, C)가 올바른 답이다.

  • BB와 CC는 서로 다르고, 둘 다 AA와도 다르다.
  • 오래된 나무 AA, BB, CC를 이 순서로 이으면 반시계 방향이다. 즉 세 점이 한 직선 위에 있지 않다.
  • 새 나무가 삼각형 ABCABC의 내부에 있다. 변 위에 있으면 안 된다.
  • AA, BB, CC가 아닌 오래된 나무는 삼각형 ABCABC의 내부에도, 세 변 위에도 없다.

입력

첫째 줄에 오래된 나무의 수 NN과 정원사가 이미 고른 나무의 번호 AA가 주어진다 (3≤N≤3003 \le N \le 300, 1≤A≤N1 \le A \le N).

둘째 줄에 새 나무의 좌표 xx와 yy가 주어진다.

다음 NN개 줄에는 오래된 나무의 좌표 xx와 yy가 번호 순서대로 한 줄에 한 그루씩 주어진다 (−106≤x,y≤106-10^6 \le x, y \le 10^6). N+1N + 1개의 점은 모두 서로 다르다.

출력

AA, BB, CC 순서로 올바른 보호 구역을 이루는 BB와 CC를 공백 하나로 구분해 한 줄에 출력한다.

올바른 쌍이 여러 개면 가장 작은 것을 출력한다. 먼저 BB를 비교하고, BB가 같을 때만 CC를 비교한다. 올바른 쌍이 하나도 없으면 0 0을 출력한다.

예제3

  1. 예제 1

    입력
    7 1
    9 3
    3 1
    8 7
    9 5
    11 5
    12 4
    9 1
    13 6
    
    예상 출력
    6 4
    
  2. 예제 2

    입력
    3 1
    1 1
    0 0
    4 0
    0 4
    
    예상 출력
    2 3
    
  3. 예제 3

    입력
    3 1
    5 5
    0 0
    4 0
    0 4
    
    예상 출력
    0 0