題意:
? ? ?給你一些點(diǎn),這些點(diǎn)有各自的初始位置,移動(dòng)速度和方向,問你什么時(shí)候任意兩點(diǎn)中最長(zhǎng)的距離最小,求時(shí)刻和此時(shí)的距離..

思路:

? ? ?感覺題目很贊,一開始想不到三分,因?yàn)槊从修k法證明他是凹性或者凸性函數(shù),后來師傅給我說了幾個(gè)特例,自己在想想瞬間明白了,其實(shí)仔細(xì)想下會(huì)發(fā)現(xiàn),假設(shè)我們當(dāng)前的函數(shù)是隨著x,y逐漸減小的,那么此時(shí)的某一時(shí)刻占據(jù)主要角色的那兩個(gè)點(diǎn)一定是相聚的,而且當(dāng)主角的兩個(gè)點(diǎn)換掉的時(shí)候也一定是在距離相等的地方更換的,如果當(dāng)前的是隨x增大的那么占據(jù)主角的連個(gè)點(diǎn)就一定是分散的,因?yàn)槿绻窍嗑勰敲丛谥跋嗑鄣臅r(shí)候這對(duì)就一定會(huì)是主角,而如果之前是主角那么現(xiàn)在就有可能是相交后由相聚變成分散了,畫幾個(gè)特例就ok了..

#include<stdio.h> #include<math.h>#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; }

總結(jié)

以上是生活随笔為你收集整理的hdu4717 三分(散点的移动)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。