bzoj1094[ZJOI2007]粒子运动计算几何

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

 #include<bits/stdc++.h>

 #define N 105

 using namespace std;

 int n,m,k;double t1,t2,r,c[N][N];

 struct point{

     double x,y;

     point operator + (const point &b)const{return (point){x+b.x,y+b.y};}

     point operator * (const double &b)const{return (point){x*b,y*b};}

     point operator - (const point &b)const{return (point){x-b.x,y-b.y};}

 }o;

 struct line{point p,v;}a[N][N];

 double dot(point a,point b){return a.x*b.x+a.y*b.y;}

 double crs(point a,point b){return a.x*b.y-a.y*b.x;}

 double solve(int i,int j,int p1,int p2){

     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]);

     double u=dot(v1,v1),v=*dot(v1,v2),w=dot(v2,v2),t;

     if(!u){

         if(v>)t=t1;else t=t2;

         return sqrt(w+t*v);

     }

     else{

         t=-v/(*u);

         if(t<t1)t=t1;if(t>t2)t=t2;

         return sqrt(t*t*u+v*t+w);

     }

 }

 int main(){

     scanf("%lf%lf%lf",&o.x,&o.y,&r);

     scanf("%d%d",&n,&m);

     double u,v,w,t;point p,q,nm;

     for(int i=;i<=n;i++){

         scanf("%lf%lf%lf%lf",&a[i][].p.x,&a[i][].p.y,&a[i][].v.x,&a[i][].v.y);

         for(int j=;j<=m;j++){

             p=a[i][j-].p-o;q=a[i][j-].v;

             u=dot(q,q);v=dot(p,q)*;w=dot(p,p)-r*r;

             t=(sqrt(v*v-*u*w)-v)//u;

             c[i][j]=c[i][j-]+t;

             a[i][j].p=a[i][j-].p+a[i][j-].v*t;

             nm=a[i][j].p-o;swap(nm.x,nm.y);nm.x=-nm.x;

             a[i][j].v=nm*(dot(nm,a[i][j-].v)/dot(nm,nm)*)-a[i][j-].v;

             line tmp=a[i][j];

             printf("%.2lf %.2lf %.2lf %.2lf\n",tmp.p.x,tmp.p.y,tmp.v.x,tmp.v.y);

         }

     }

     double ans=1e10;int p1,p2;

     for(int i=;i<=n;i++)

         for(int j=i+;j<=n;j++){

             p1=p2=;

             while(p1<m&&p2<m){

                 t1=max(c[i][p1],c[j][p2]);

                 t2=min(c[i][p1+],c[j][p2+]);

                 ans=min(ans,solve(i,j,p1,p2));

                 if(c[i][p1+]<c[j][p2+])p1++;

                 else p2++;

             }

         }

     printf("%.3lf\n",ans);

     return ;

 }

巴特西

bzoj1094[ZJOI2007]粒子运动计算几何

1094: [ZJOI2007]粒子运动

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

巴特西

bzoj1094[ZJOI2007]粒子运动 计算几何

1094: [ZJOI2007]粒子运动

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

bzoj1094[ZJOI2007]粒子运动计算几何