[BOJ 14403] 스프링클러

View as PDF

Submit solution

Points: 2
Time limit: 2.0s
Memory limit: 512M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

영선이는 마당에서 꽃을 키운다. 영선이는 자연스럽게 키우는 것을 좋아하기에 꽃을 최대한 자연스럽게, 잡초 마냥, 이곳 저곳에 심었다. 그러나 꽃을 너무 이곳 저곳에 심어 꽃에 물을 주기가 힘들게 되었다.</p>

그래서 영선이는 스프링클러를 2개를 사와서 설치를 하였다. 각 스프링클러는 각자 r1,r2을 반지름을 갖는 원 영역만큼 물을 뿌린다. 영선이는 이 물이 뿌려지는 원의 반지름을 조절하여 모든 꽃에 물을 뿌리려 한다. 모든 꽃은 둘 중 한 군데에서라도 물을 받으면 된다. 꽃이 스프링클러에서 물을 받으려면 꽃과 스프링클러의 좌표를 (x1,y1),(x2,y2)라고 할 때, sqrt((x1-x2)^2+(y1-y2)^2) ≤ r 이어야 한다.

물이 뿌려지는 것은 원의 영역이기 때문에 (r1^2+r2^2)*π만큼 뿌려지는데, 물을 아끼기 위하여 저 값을 최소로 하고 싶다. 하지만 계산의 편의상 π는 무시하고 계산한다. 따라서 r1^2+r2^2의 값을 최소로 할 때, 그 값을 출력하시오.

입력 형식

첫째 줄에는 꽃의 개수 n, 두 스프링클러의 좌표 x1,y1,x2,y2가 주어진다.(1≤n≤2000, -1,000,000≤ x1,y1,x2,y2 ≤ 1,000,000)</p>

다음 n줄에는 각 꽃의 좌표 x,y가 주어진다. 모든 꽃과 스프링클러의 좌표는 다름이 보장된다.(-1,000,000 ≤ x,y ≤ 1,000,000)

출력 형식

r1^2+r2^2의 값을 최소로 할 때, 그 값을 출력하시오.

예제 입력

4 0 0 5 0
9 4
8 3
-1 0
1 4

예제 출력

33

Comments

There are no comments at the moment.