1094: [ZJOI2007]粒子運動

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?658??Solved:?164
[Submit][Status][Discuss]

Description

　　阿Q博士正在觀察一個圓形器皿中的粒子運動。不妨建立一個平面直角坐標系，圓形器皿的圓心坐標為(x0, y0
)，半徑為R。器皿中有若干個粒子，假設第i個粒子在時刻0的位置為(xi, yi)，速度為(vxi,vyi)（注：這是一個
速度向量，若沒有發生碰撞，t時刻的位置應該是(xi + t * vxi, yi + t * vyi) ）。假設所有粒子的運動互不干
擾；若某個粒子在某個時刻碰到了器皿壁，將發生完全彈性碰撞，即速度方向按照碰撞點的切線鏡面反射，且速度
大小不變（如圖）。認為碰撞是瞬間完成的。

　　盡管碰撞不會影響粒子的速率，但是粒子卻會受到一定的傷害，所以若某一個粒子碰撞了k次器皿壁，那么在
第k次碰撞時它便會消亡。 出于研究的需要，阿Q博士希望知道從時刻0到所有粒子都消亡這段時間內，所有粒子之
間的最近距離是什么。你能幫助他么？

Input

　　第一行包含三個實數，分別為x0, y0, R，即圓形器皿的圓心坐標及半徑。第二行包含兩個正整數N, k，分別
表示粒子的總數與消亡碰撞次數。接下來N行每行四個實數，分別為xi, yi, vxi , vyi，保證(xi, yi)都在圓內且
(vxi, vyi)非零。

Output

　　僅包含一個實數，即所有粒子的歷史最近距離，精確到小數點后三位。

Sample Input

0 0 10
2 10
0 -5 0 1
5 0 1 0

Sample Output

7.071

HINT

?

　　對于所有的數據，2 ≤N ≤100。1≤k ≤100。 請注意實數精度問題。

?

暴力枚舉兩個點，判斷它們在每一時刻的最短距離
兩個點的運動其實是分段的，每當一個點碰邊就重新劃分一段，最多可能有2*k段
每次碰邊后重新計算路線，計算方式看這個博客http://blog.csdn.net/lych_cys/article/details/50785713

?

1 #include<bits/stdc++.h> 2 #define N 105 3 using namespace std; 4 int n,m,k;double t1,t2,r,c[N][N]; 5 struct point{ 6 double x,y; 7 point operator + (const point &b)const{return (point){x+b.x,y+b.y};} 8 point operator * (const double &b)const{return (point){x*b,y*b};} 9 point operator - (const point &b)const{return (point){x-b.x,y-b.y};} 10 }o; 11 struct line{point p,v;}a[N][N]; 12 double dot(point a,point b){return a.x*b.x+a.y*b.y;} 13 double crs(point a,point b){return a.x*b.y-a.y*b.x;} 14 double solve(int i,int j,int p1,int p2){ 15 point v1=a[i][p1].v-a[j][p2].v,v2=(a[i][p1].p-a[i][p1].v*c[i][p1])-(a[j][p2].p-a[j][p2].v*c[j][p2]); 16 double u=dot(v1,v1),v=2*dot(v1,v2),w=dot(v2,v2),t; 17 if(!u){ 18 if(v>0)t=t1;else t=t2; 19 return sqrt(w+t*v); 20 } 21 else{ 22 t=-v/(2*u); 23 if(t<t1)t=t1;if(t>t2)t=t2; 24 return sqrt(t*t*u+v*t+w); 25 } 26 } 27 int main(){ 28 scanf("%lf%lf%lf",&o.x,&o.y,&r); 29 scanf("%d%d",&n,&m); 30 double u,v,w,t;point p,q,nm; 31 for(int i=1;i<=n;i++){ 32 scanf("%lf%lf%lf%lf",&a[i][0].p.x,&a[i][0].p.y,&a[i][0].v.x,&a[i][0].v.y); 33 for(int j=1;j<=m;j++){ 34 p=a[i][j-1].p-o;q=a[i][j-1].v; 35 u=dot(q,q);v=dot(p,q)*2;w=dot(p,p)-r*r; 36 t=(sqrt(v*v-4*u*w)-v)/2/u; 37 c[i][j]=c[i][j-1]+t; 38 a[i][j].p=a[i][j-1].p+a[i][j-1].v*t; 39 nm=a[i][j].p-o;swap(nm.x,nm.y);nm.x=-nm.x; 40 a[i][j].v=nm*(dot(nm,a[i][j-1].v)/dot(nm,nm)*2)-a[i][j-1].v; 41 line tmp=a[i][j]; 42 printf("%.2lf %.2lf %.2lf %.2lf\n",tmp.p.x,tmp.p.y,tmp.v.x,tmp.v.y); 43 } 44 } 45 double ans=1e10;int p1,p2; 46 for(int i=1;i<=n;i++) 47 for(int j=i+1;j<=n;j++){ 48 p1=p2=0; 49 while(p1<m&&p2<m){ 50 t1=max(c[i][p1],c[j][p2]); 51 t2=min(c[i][p1+1],c[j][p2+1]); 52 ans=min(ans,solve(i,j,p1,p2)); 53 if(c[i][p1+1]<c[j][p2+1])p1++; 54 else p2++; 55 } 56 } 57 printf("%.3lf\n",ans); 58 return 0; 59 }

?

轉載于:https://www.cnblogs.com/wsy01/p/8177042.html

總結

以上是生活随笔為你收集整理的bzoj1094[ZJOI2007]粒子运动 计算几何的全部內容，希望文章能夠幫你解決所遇到的問題。

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