ZOJ Trick or Treat//3분 찾기
Time Limit: 5 Seconds Memory Limit: 65536 KB Special Judge
Johnny and his friends have decided to spend Halloween night doing the usual candy collection from the households of their village. As the village is too big for a single group to collect the candy from all houses sequentially, Johnny and his friends have decided to split up so that each of them goes to a different house, collects the candy (or wreaks havoc if the residents don't give out candy), and returns to a meeting point arranged in advance.
There are n houses in the village, the positions of which can be identified with their Cartesian coordinates on the Euclidean plane. Johnny's gang is also made up of n people (including Johnny himself). They have decided to distribute the candy after everybody comes back with their booty. The houses might be far away, but Johnny's interest is in eating the candy as soon as possible.
Keeping in mind that, because of their response to the hospitality of some villagers, some children might be wanted by the local authorities, they have agreed to fix the meeting point by the river running through the village, which is the line y = 0. Note that there may be houses on both sides of the river, and some of the houses may be houseboats (y = 0). The walking speed of every child is 1 meter per second, and they can move along any direction on the plane.
At exactly midnight, each child will knock on the door of the house he has chosen, collect the candy instantaneously, and walk back along the shortest route to the meeting point. Tell Johnny at what time he will be able to start eating the candy.
Input
Each test case starts with a line indicating the number n of houses (1 ≤ n ≤ 50 000). The next n lines describe the positions of the houses; each of these lines contains two floating point numbers x and y (-200 000 ≤ x, y ≤ 200 000), the coordinates of a house in meters. All houses are at different positions.
A blank line follows each case. A line with n = 0 indicates the end of the input; do not write any output for this case.
Output
For each test case, print two numbers in a line separated by a space: the coordinate x of the meeting point on the line y = 0 that minimizes the time the last child arrives, and this time itself (measured in seconds after midnight). Your answer should be accurate to within an absolute or relative error of 10-5.
Sample Input
2
1.5 1.5
3 0
1
0 0
4
1 4
4 4
-3 3
2 4
5
4 7
-4 0
7 -6
-2 4
8 -5
0
Sample Output
1.500000000 1.500000000
0.000000000 0.000000000
1.000000000 5.000000000
3.136363636 7.136363636
Source: Southwestern Europe Regional Contest 2009
#include
#include
const double eps=1e-10;
struct T
{
double x,y;
}t[50005];
double fir,sec;
int n;
double check(double x)
{
double max=0;
for(int i=0;i
return max;
}
void solve()
{
double mid1,mid2;
mid1=(fir+sec)/2;
while(sec-fir>eps)
{
mid1=(fir+sec)/2;
mid2=(mid1+sec)/2;
double t1=check(mid1);
double t2=check(mid2);
if(t1
}
printf("%0.9lf %0.9lf/n",mid1,check(mid1));
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
fir=200000;
sec=-200000;
for(int i=0;i
scanf("%lf%lf",&t[i].x,&t[i].y);
if(t[i].x
}
//if(n==1) printf("%0.9lf %0.9lf/n",t[0].x,t[0].y);
//else
solve();//나는 왜 위에 그 문장을 넣었는지 모르겠다. 그것은 틀렸다
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Ruby의 구조체 클래스은 접근자 메서드가 있는 속성 모음입니다. 클래스를 명시적으로 작성할 필요 없이. Struct 클래스는 구성원 및 해당 값 집합을 포함하는 새 하위 클래스를 생성합니다. 각 멤버에 대해 #attr_accessor 와...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.