/**//* 题意: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
搜索
最新评论
|
|