hdu4717:http://acm.hdu.edu.cn/showproblem.php?pid=4717

題意：給你n個點的坐標，然后每個點都有一個速度，求在什么時刻任意兩個點的最大距離最小，以及這個距離。

題解：畫個圖，發現可以用3分來做，但是自己敲了個二分，只不過二分的時候要注意方向，其實這個和三分區別不是很大。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 const int N=303; 8 const double eps=1e-5; 9 double xx[N],yy[N],vx[N],vy[N]; 10 int n,m; 11 double t,len; 12 double dis(int a,int b,double t){ 13 return sqrt((xx[a]-xx[b]+(vx[a]-vx[b])*t)*(xx[a]-xx[b]+(vx[a]-vx[b])*t)+(yy[a]-yy[b]+(vy[a]-vy[b])*t)*(yy[a]-yy[b]+(vy[a]-vy[b])*t)); 14 } 15 double getmax(double t){ 16 double maxn=0; 17 for(int i=1;i<=n;i++){ 18 for(int j=i+1;j<=n;j++){ 19 maxn=max(maxn,dis(i,j,t)); 20 } 21 } 22 return maxn; 23 } 24 void solve(){ 25 double l=0,r=1000000000; 26 t=10000000,len=10000000; 27 while(abs(l-r)>eps){ 28 double mid=(l+r)/2; 29 double temp1=getmax(mid); 30 double temp2=getmax(mid-eps); 31 if(temp2>temp1){ 32 l=mid; 33 } 34 else{ 35 r=mid-eps; 36 t=mid-eps; 37 len=temp2; 38 } 39 } 40 } 41 int main(){ 42 int T,tt=1; 43 scanf("%d",&T); 44 while(T--){ 45 scanf("%d",&n); 46 for(int i=1;i<=n;i++){ 47 scanf("%lf%lf%lf%lf",&xx[i],&yy[i],&vx[i],&vy[i]); 48 } 49 solve(); 50 printf("Case #%d: %.2f %.2f\n",tt++,t,len); 51 } 52 } View Code

?

轉載于:https://www.cnblogs.com/chujian123/p/3923880.html

總結

以上是生活随笔為你收集整理的The Moving Points的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。