# The Moving Points

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 612    Accepted Submission(s): 250

Problem Description

There are N points in total. Every point moves in certain direction and certain speed. We want to know at what time that the largest distance between any two points would be minimum. And also, we require you to calculate that minimum distance. We guarantee that no two points will move in exactly same speed and direction.

Input

The rst line has a number T (T <= 10) , indicating the number of test cases. For each test case, first line has a single number N (N <= 300), which is the number of points. For next N lines, each come with four integers Xi, Yi, VXi and VYi (-106 <= Xi, Yi <= 106, -102 <= VXi , VYi <= 102), (Xi, Yi) is the position of the ith point, and (VXi , VYi) is its speed with direction. That is to say, after 1 second, this point will move to (Xi + VXi , Yi + VYi).

Output

For test case X, output "Case #X: " first, then output two numbers, rounded to 0.01, as the answer of time and distance.

Sample Input

2 2 0 0 1 0 2 0 -1 0 2 0 0 1 0 2 1 -1 0

Sample Output

Case #1: 1.00 0.00 Case #2: 1.00 1.00

Source

2013 ACM/ICPC Asia Regional Online —— Warmup2

Recommend

zhuyuanchen520

``` 1 #include<iostream>
2 #include<vector>
3 #include<cstdio>
4 #include<cstring>
5 #include<cstdlib>
6 #include<cmath>
7 #define MAX 1e9
8 #define exp 1e-6
9 using namespace std;
10    //设置结构体
11 typedef struct
12 {
13     int x,y;
14     int px,py;
15 }point;
16
17    //计算任意时间两点的距离
18 double das(point a,point b,double t )
19 {
20     return  sqrt(pow(((a.x+a.px*t)-(b.x+b.px*t)),2)+pow(((a.y+a.py*t)-(b.y+b.py*t)),2));
21 }
22    //判断两个数最大值....
23 double max( double a,double b)
24 {
25     return a>b?a:b;
26 }
27 point po[305];
28  int main()
29  {
30     int n,i,j,cnt=1,t;
31     double ll,rr,ml,mr,ans1,ans2;
32     scanf("%d",&t);
33     while(t--)
34     {
35       scanf("%d",&n);
36       for( i=1 ; i<=n ; i++ )
37       {
38        scanf("%d%d%d%d",&po[i].x,&po[i].y,&po[i].px,&po[i].py);
39        //cin>>po[i].x>>po[i].y>>po[i].px>>po[i].py;
40       }
41      //没有其他的办法，除了遍历之外
42       ll=0.0,rr=MAX;
43      while(rr-ll>exp)
44      {
45         ans1=ans2=0.0;
46         //ml=(ll+rr)/2.0;   //慢很多
47          //mr=(ml+rr)/2.0;
48         ml=(ll*2+rr)/3.0;       // r/3.0  较快
49         mr=(ll+rr*2)/3.0;       // 2*r/3.0
50        for( i=1 ; i<n ; i++ )
51        {
52          for( j=i+1 ; j<=n ;j++ )
53          {
54              ans1=max(ans1,das(po[i],po[j],ml));  //对左边
55              ans2=max(ans2,das(po[i],po[j],mr));  //对右边
56          }
57        }
58         if( ans1<ans2 )
59               rr=mr;
60         else
61              ll=ml;
62      }
63        //得到时间ll or rr 都可以
64       ans1=0.0;
65       for(i=1 ; i<n ; i++ )
66        {
67          for(j=1+i ; j<=n ;j++)
68          {
69              ans1=max(ans1,das(po[i],po[j],ll));  //对左边ll/rr
70          }
71      }
72      printf("Case #%d: %.2lf %.2lf\n",cnt++,ll,ans1);
73     }
74     return 0;
75  }```

657 篇文章64 人订阅

0 条评论

## 相关文章

35140

### HDUOJ-------（1022）Train Problem I

Train Problem I Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32...

31970

### HDU 1000 A + B Problem(指针版)

A + B Problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

28540

35760

### HDU 2476 String painter（区间DP）

String painter Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/327...

35980

### HDUOJ----(1030)Delta-wave

Delta-wave Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K...

35670

### HDU 5877 2016大连网络赛 Weak Pair(树状数组，线段树，动态开点，启发式合并，可持久化线段树)

Weak Pair Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144...

413100

### PAT 1008 Elevator

1008. Elevator (20) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 ...

33450

### HDU 5157 Harry and magic string(回文树)

Harry and magic string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...

37580

### POJ 2484 A Funny Game(智商博弈)

Description Alice and Bob decide to play a funny game. At the beginning of the ...

37980