그를 안에 가둬라
면접 대비시간 제한1초메모리 제한512 MB
볼록 다각형의 꼭짓점에 있는 경비병들과 내부의 죄수 위치가 주어질 때, 합이 1이고 가중 평균이 죄수 위치가 되는 음이 아닌 가중치를 구한다.
문제
마법사와 오크 사이의 오랜 전쟁의 결과로, 당신은 교도소 블록 중 하나의 관리관으로 임명되었다. 최근 오크의 지도자가 잡혀 특수 감방에 갇혔다. 감방은 다음과 같이 동작한다. 감방은 볼록 다각형이고, 각 꼭짓점에는 마법사가 배치된 감시탑이 있다.
마법사와 오크 사이의 최근 합의인 "감방 내 수감자를 위한 유익한 활동" 덕분에, 오크의 지도자는 감방 안에서 자유롭게 움직일 수 있어야 한다. 당신은 수감자가 탈출하는 것을 원하지 않으므로, 마법사들에게 협력하여 봉쇄 주문을 시전하라고 명령한다. 제대로 시전되면, 이는 수감자 주위에 마법의 아우라를 만들어 탈출을 막는다.
봉쇄 주문이 작동하려면, 모든 마법사가 자신의 최대 마력의 일정 비율을 주문에 쏟아야 하며, 다음 두 가지가 성립해야 한다.
- 주문은 완벽하게 균형을 이루어야 한다. 모든 마법사의 마력 비율의 합은 1이어야 한다.
- 주문의 중심은 수감자와 일치해야 한다. 즉, 마법사들이 쏟는 마력 비율로 가중 평균한 마법사들의 위치가 수감자의 위치여야 한다.
감방의 배치와 수감자의 위치가 주어졌을 때, 봉쇄 주문이 작동하도록 각 마법사가 사용해야 할 마력 비율을 정하라.
그림 K.1: 예제 1의 감방. S1, S2, S3는 마법사이고 P는 수감자이다. (1/3)S1 + (1/3)S2 + (1/3)S3 = 1/3(0, 0) + 1/3(3, 0) + 1/3(0, 3) = (1, 1) = P임에 주목하라.
입력
- 첫 번째 줄에는 감시탑에 있는 마법사의 수 3 ≤ n ≤ 10과 수감자의 좌표인 두 정수 −10^4 ≤ x, y ≤ 10^4가 주어진다.
- 다음 n개의 줄에는 각각 마법사 한 명의 좌표인 두 정수 −10^4 ≤ x, y ≤ 10^4가 주어진다.
좌표는 반시계 방향 순서로 주어지며, 엄격한 볼록 다각형을 이룬다. 즉, 세 점이 한 직선 위에 있지 않다. 수감자는 다각형의 엄격한 내부에 있다.
출력
- i번째 줄에 i번째 마법사가 봉쇄 주문이 작동하도록 사용해야 할 마력 비율을 0과 1 사이의 부동소수점 수로 출력한다.
가능한 해가 여러 개라면, 그중 아무거나 출력해도 된다.
비율의 합이 1과 10^−4 이내로 차이 나고, 주문의 가중 중심이 수감자로부터 10^−4 이내 거리에 있으면 정답으로 인정된다. 답 자체를 10^−4 정밀도로 출력하는 것만으로는 충분하지 않을 수 있다.