首页 > ACM题库 > HDU-杭电 > HDU 4717-The Moving Points-分治-[解题报告]HOJ
2015
09-17

HDU 4717-The Moving Points-分治-[解题报告]HOJ

The Moving Points

问题描述 :

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.

输入:

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).

输出:

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).

样例输入:

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

样例输出:

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

/*【题意】:
给N个点,给出N个点的方向和移动速度,求每个时刻N个点中任意两点的最大值中的最小值,以及取最小值的时刻
解析:
两个点为例,任意两个点,按照自己的方向移动,一般情况下是,先两点慢慢接近,直到最近距离,然后慢慢远离,后面越来越远,图像画出来有点像抛物线,
这题就是抛物线求最小值,三分:先二分时间,按照斜率确定移动方向,直到移动到抛物线的最低端
 注意题目精度,每次最好分1e-5以上,才能保证正确性
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int maxn=310;
#define exp  1e-6
int n;
struct point
{
	double x,y;
	double vx,vy;
}p[maxn];
double dis(int a,int b,double k)
{
	return sqrt( 1.0*(p[a].x+p[a].vx*k-p[b].x-p[b].vx*k)*(p[a].x+p[a].vx*k-p[b].x-p[b].vx*k)+
		         1.0*(p[a].y+p[a].vy*k-p[b].y-p[b].vy*k)*(p[a].y+p[a].vy*k-p[b].y-p[b].vy*k) );
}
double okboy(double k)
{
      int i,j;
	  double max=-1;
      for(i=0;i<n;i++)
	  {
		  for(j=i+1;j<n;j++)
		  {
			  double sb=dis(i,j,k);
			  if(sb>max) max=sb;
		  }
	  }
	  return max;
}
void sanfen()
{
	double l=0,r=1e8,min=(double)0x3f3f3f3f,t,mid;
	while(l<r)
	{
		 mid=(l+r)/2;
		double ok1=okboy(mid);
		double ok2=okboy(mid-exp);//三分时间
		if(ok1<ok2) l=mid+exp;
		else r=mid-exp;
		if(min>ok1)
		{
			min=ok1;
			t=mid;
		}
	}
	printf("%.2lf %.2lf\n",t,min);
}
int main()
{
	int i;
	int t,cas=0;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i].vx,&p[i].vy);
		printf("Case #%d: ",++cas);
		sanfen();
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/wzj792506536/article/details/11605091