 /**//*
题意:n只鸟在n个位置(n<=9) 一个人可以按一定顺序放鸟,放完一只后需要休息时间t
才能放下一只,问最少的时间使得这些鸟都在一个地方碰头
给出鸟的速度范围,x方向<=vx , y方向<=vy

由于n<=9 全排列枚举顺序
然后二分时间T,而一只鸟飞行的范围就是
[x-vx*t',x+vx*t'],[y-vy*t',y+vy*t']
t' = max(T-(i-1)*t , 0) 注意这里可以取0,即不飞行!!!
*/
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const double EPS = 1e-8;//1e-6 is also ok

struct Point
  {
double x,y;
int id;
void read()
 {
scanf("%lf%lf",&x,&y);
}
bool operator < (const Point &B)const
 {
return id < B.id;
}
};

Point pt[10];
int n , vx , vy ,t;

bool chk(double endTime)
  {
double xMin = -1e30 , yMin = -1e30;
double xMax = 1e30 , yMax = 1e30;
double left = endTime;

for(int i = 0 ; i < n ; i++)
 {
double _xMin = pt[i].x - left*vx , _yMin = pt[i].y - left*vy;
double _xMax = pt[i].x + left*vx , _yMax = pt[i].y + left*vy;

xMin = max(xMin , _xMin);
xMax = min(xMax , _xMax);
if(xMin > xMax + EPS)return false;

yMin = max(yMin , _yMin);
yMax = min(yMax , _yMax);
if(yMin > yMax + EPS)return false;

left -= t;

if(left < 0)left = 0;//需要这样子!!有些鸟可以不用飞出去
}
return true;
}

int main()
  {
//freopen("in","r",stdin);

while( ~scanf("%d%d%d%d",&n,&vx,&vy,&t) )
 {
for(int i = 0; i < n ; i++)
 {
pt[i].read();
pt[i].id = i;
}

double ans = 1e30;
do
 {
int cnt = 0;
double low = 0, high = 1e10;
//if(chk(high)==false) continue; high is absolutely ok , not need to check
while(high - low > EPS && cnt < 100)
 {
double mid = (high + low)/2;
if(chk(mid))high = mid;
else low = mid;
cnt ++;
}
ans = min(ans,high);

}while(next_permutation(pt,pt+n));

printf("%f\n",ans);
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|