凹凸曼和小怪兽的故事

凹凸曼和小怪兽的故事"/>

凹凸曼和小怪兽的故事

Description

世界末日来了，凹凸曼和小怪兽们开始进行最后一次较量！这次决战总共有n个凹凸曼和n个小怪兽，位置以坐标形式给出。因为是最后一次战斗，所以无论是哪一边都想要赢得第一场角逐，于是双方都想要找出最近的那一对凹凸曼和小怪兽，凹凸曼和小怪兽的速度分别为a和b（单位长度每秒）。不过，凹凸曼和小怪兽的智商相信有童年的童鞋们都明白，写个程序帮他们算算最早的角逐需要多长时间开始吧，凹凸曼和小怪兽遇到了就会开始角逐,而且它们会相向而行。

Input

第一行给出n，a，b三个整数(0<n<100000);

接下来的n行给出凹凸曼位置，每行两个整数x，y(0≤x,y≤1000000000);

再接下来的n行给出小怪兽位置，每行两个整数x，y(0≤x,y≤1000000000);

Output

对于每一组数据输出最短开始角逐的时间 

Sample Input

4 1 2 0 0 0 1 1 0 1 1 2 2 2 3 3 2 3 3 4 100 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output

0.471 0.000

/*用二分的方法做，先将X从小到大排序，然后二分找出之间最小距离，这是算出了X最近的距离，
比如这之间的点的最小距离是ans，然后我们只要把 x>=mid-ans && x<=mid+ans中的点放进另外一个
数组中再以Y从小到大的排序再找一次之间最小距离。这样就可以找出全部点中的最小距离。*/#include <stdio.h>
#include <algorithm>
#include <math.h>
#define MAXN 100005
using namespace std;struct node
{double x,y;bool operator<(node a) const{return x<a.x;}
} A[MAXN],B[MAXN];
//二分算出x的最小距离
int search(int n,double key)
{int l=1,r=n+1,mid;while (r-l>1){mid=l+r>>1;if (B[mid].x<key) l=mid;else  r=mid;}return l;
}int main()
{int n,i,t1,t2,v1,v2;while (~scanf("%d%d%d",&n,&v1,&v2)){for (i=1; i<=n; i++) scanf("%lf%lf",&A[i].x,&A[i].y);for (i=1; i<=n; i++) scanf("%lf%lf",&B[i].x,&B[i].y);sort(A+1,A+1+n);sort(B+1,B+1+n);double ans=1e30;for (t1=1; t1<=n; t1++)for (t2=search(n,A[t1].x-ans); t2<=n && B[t2].x-A[t1].x<ans; t2++)ans=min(ans,sqrt((A[t1].x-B[t2].x)*(A[t1].x-B[t2].x)+(A[t1].y-B[t2].y)*(A[t1].y-B[t2].y)));//A B之间的距离printf("%.3lf\n",ans/(v1+v2));}return 0;
}

 

转载于:.html