hdu4717 三分(散点的移动)
阅读原文时间:2023年07月08日阅读:2

**题意:

     给你一些点,这些点有各自的初始位置,移动速度和方向,问你什么时候任意两点中最长的距离最小,求时刻和此时的距离..

思路:
**

感觉题目很赞,一开始想不到三分,因为么有办法证明他是凹性或者凸性函数,后来师傅给我说了几个特例,自己在想想瞬间明白了,其实仔细想下会发现,假设我们当前的函数是随着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; }

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章