HDUOJ---The Moving Points

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  }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 2502 月之数(二进制,规律)

月之数 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

35140
来自专栏ml

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
来自专栏杨熹的专栏

【LEETCODE】模拟面试-134-Gas Station

新生 题目: https://leetcode.com/problems/gas-station/ There are N gas stations alon...

35760
来自专栏算法修养

HDU 2476 String painter(区间DP)

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

35980
来自专栏ml

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

扫码关注云+社区

领取腾讯云代金券