 /**//*
題意:n只鳥(niǎo)在n個(gè)位置(n<=9) 一個(gè)人可以按一定順序放鳥(niǎo),放完一只后需要休息時(shí)間t
才能放下一只,問(wèn)最少的時(shí)間使得這些鳥(niǎo)都在一個(gè)地方碰頭
給出鳥(niǎo)的速度范圍,x方向<=vx , y方向<=vy

由于n<=9 全排列枚舉順序
然后二分時(shí)間T,而一只鳥(niǎo)飛行的范圍就是
[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;//需要這樣子!!有些鳥(niǎo)可以不用飛出去
}
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;
}
|