http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1309
题意:
给出凹凸曼和小怪兽的坐标,然后求出一对最近的凹凸曼和怪兽,算出他们的距离
然后除以他们的速度之和。
坑爹:
最小点对的一个模板,就只是要判断一下是不同种类(超人或怪兽)的点才可以计算就行了。
解法:
用二分的方法做,先将X从小到大排序,然后二分找出之间最小距离,这是算出了X最近的距离,
比如这之间的点的最小距离是ans,然后我们只要把 x>=mid-ans && x<=mid+ans中的点放进另外一个
数组中再以Y从小到大的排序再找一次之间最小距离。这样就可以找出全部点中的最小距离。
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 7 const int maxn = 100000 + 10; 8 const double INF = 1000000000 * 2.0; 9 10 struct Node { 11 double x; 12 double y; 13 bool type;//0超人,1怪兽 14 }node[maxn],node2[maxn]; 15 int n; 16 17 double Min(double a,double b) 18 { 19 return a > b ? b : a; 20 } 21 22 double Count(Node a,Node b) 23 { 24 return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); 25 } 26 27 double cmpX(Node a,Node b) 28 { 29 return a.x < b.x; 30 } 31 32 double cmpY(Node a,Node b) 33 { 34 return a.y < b.y; 35 } 36 37 double Clost(int begin,int end) 38 { 39 if(begin + 1 == end && node[begin].type != node[end].type) 40 { 41 return Count(node[begin],node[end]); 42 } 43 else if(node[begin].type == node[end].type) 44 { 45 return INF; 46 } 47 if(begin + 2 == end) 48 { 49 int ans1 = INF; 50 int ans2 = INF; 51 int ans3 = INF; 52 if(node[begin].type != node[end].type) 53 { 54 ans1 = Count(node[begin],node[end]); 55 } 56 if(node[begin+1].type != node[end].type) 57 { 58 ans2 = Count(node[begin+1],node[end]); 59 } 60 if(node[begin].type != node[begin+1].type) 61 { 62 ans3 = Count(node[begin],node[begin+1]); 63 } 64 return Min(ans1,Min(ans2,ans3)); 65 } 66 int mid = (begin + end) / 2; 67 double ans = Min(Clost(begin,mid),Clost(mid+1,end)); 68 int i; 69 int cnt = 0; 70 for(i=begin; i<=end; i++) 71 { 72 if(node[i].x >= node[mid].x - ans && node[i].x <= node[mid].x + ans) 73 { 74 node2[cnt++] = node[i]; 75 } 76 } 77 sort(node2,node2+cnt,cmpY); 78 int j; 79 for(i=0; i<cnt; i++) 80 { 81 for(j=i+1; j<cnt; j++) 82 { 83 if(node2[j].y - node2[i].y >= ans) 84 { 85 break; 86 } 87 if(node2[j].type != node2[i].type) 88 { 89 ans = Min(ans,Count(node2[i],node2[j])); 90 } 91 } 92 } 93 return ans; 94 } 95 96 int main() 97 { 98 int a; 99 int b; 100 while(scanf("%d%d%d",&n,&a,&b) != EOF) 101 { 102 int i; 103 for(i=0; i<n; i++) 104 { 105 scanf("%lf%lf",&node[i].x,&node[i].y); 106 node[i].type = 0; 107 } 108 for(i=n; i<2*n; i++) 109 { 110 scanf("%lf%lf",&node[i].x,&node[i].y); 111 node[i].type = 1; 112 } 113 sort(node,node+n,cmpX); 114 double ans = Clost(0,2*n-1); 115 printf("%.3lf\n",ans/abs(a+b)); 116 } 117 return 0; 118 }