**题意:
给你一些点,这些点有各自的初始位置,移动速度和方向,问你什么时候任意两点中最长的距离最小,求时刻和此时的距离..
思路:
**
感觉题目很赞,一开始想不到三分,因为么有办法证明他是凹性或者凸性函数,后来师傅给我说了几个特例,自己在想想瞬间明白了,其实仔细想下会发现,假设我们当前的函数是随着x,y逐渐减小的,那么此时的某一时刻占据主要角色的那两个点一定是相聚的,而且当主角的两个点换掉的时候也一定是在距离相等的地方更换的,如果当前的是随x增大的那么占据主角的连个点就一定是分散的,因为如果是相聚那么在之前相聚的时候这对就一定会是主角,而如果之前是主角那么现在就有可能是相交后由相聚变成分散了,画几个特例就ok了..
#include
#include
#define INF 1000000
#define N 300 + 50
#define eps 1e-6
typedef struct
{
double x ,y;
double vx ,vy;
}NODE;
NODE node[N**];
inline double** dis(NODE A ,NODE B)
{
return ((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y**));
}
inline double** maxx(double x ,double y)
{
return x > y ? x : y**;
}
double** now_dis(int n ,double mid)
{
double now_max = 0;
for(int i = 1 ;i <= n ;i ++)
for(int j = i + 1 ;j <= n ;j ++)
{
NODE A ,B;
A.x = node[i].x + mid * node[i].vx;
A.y = node[i].y + mid * node[i].vy;
B.x = node[j].x + mid * node[j].vx;
B.y = node[j].y + mid * node[j].vy;
now_max = maxx(now_max ,dis(A ,B));
}
return now_max**;
}
double** abss(double x)
{
return x > 0 ? x : -x**;
}
int main ()
{
int** t ,n ,i ,cas = 1;
scanf("%d" ,&t);
while(t--)
{
scanf("%d" ,&n);
for(i = 1 ;i <= n ;i ++)
scanf("%lf %lf %lf %lf" ,&node[i].x ,&node[i].y ,&node[i].vx ,&node[i].vy);
double low ,up ,mid ,mmid;
low = 0 ,up = INF;
double dis1 ,dis2;
while(1)
{
mid = (low + up) / 2;
mmid = (mid + up) / 2;
dis1 = now_dis(n ,mid);
dis2 = now_dis(n ,mmid);
if(dis1 > dis2) low = mid;
else up = mmid;
if(abss(low - up) < eps) break;
}
printf("Case #%d: %.2lf %.2lf\n" ,cas ++ ,low ,sqrt(dis1));
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章