34240번 - 반원 스페셜 저지

문제

2ドル$차원 좌표평면상의 점 $N$개와 반원 하나가 주어진다.

$(x_1, y_1)$ 위치에 있는 점 하나를 $(x_2, y_2)$ 위치로 옮기려면 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$만큼의 비용이 든다. 이때, 점을 반드시 정수 좌표 위치로 옮길 필요는 없다. 모든 점을 반원 안으로 옮기는 데 드는 최소 비용을 구하여라. 반원의 경계선 위에 있는 점은 반원 안에 있는 것으로 간주한다.

입력

첫째 줄에 점의 개수 $N$이 주어진다. $(1 \leq N \leq 100,000円)$

둘째 줄부터 $N$개의 줄에 걸쳐 각 점의 $x$좌표와 $y$좌표가 공백으로 구분되어 주어진다. $(-1,000円 \leq x, y \leq 1,000円)$

마지막 줄에 반원을 나타내는 두 점 $A$와 $B$의 좌표 $x_A, y_A, x_B, y_B$가 공백으로 구분되어 주어진다. $A$와 $B$의 좌표는 다르다. $(-1,000円 \leq x_A, y_A, x_B, y_B \leq 1,000円)$

점 $A$는 원의 중심이며, 점 $B$는 원의 둘레 위에 있는 점이다. $A$를 중심으로 하고 $B$를 지나는 원을 그렸을 때, 반원은 점 $A$에서 $B$로 향하는 선분의 방향을 기준으로 왼쪽 절반의 영역이다.

주어지는 모든 좌표는 정수이다.

출력

첫째 줄에 모든 점을 반원 안으로 옮기는 데 드는 최소 비용을 출력한다. 실제 정답과 출력값의 절대 오차 또는 상대 오차가 10ドル^{-6}$ 이하라면 정답으로 인정한다.

제한

힌트