【bzoj1094】[ZJOI2007]粒子运动

2015.06.24 12:48 Wed | 32次阅读 | 旧日oi | 固定链接 | 源码

题目大意

给定1个圆,圆里有一些粒子,每个粒子有一个初始位置和初始速度,碰撞k次边界后消失,求从开始到结束所有粒子之间的最近距离。n<=100,k<=100

题解

这并不是很高深的算法,就是单纯的模拟,但是能1个小时完完全全自己写出来还是蛮开心的~
大致思路:对于每个读入的点,预处理出每次的碰撞时间,碰撞点和碰撞后的速度。然后枚举两个点,在上一次有点碰到边界和这一次中间,两点之间的距离是一个二次函数,求一下最小值就行。
看起来蛮难写的,但是其实写起来很简单,都是初中知识嘛~

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define db double
db x2,y2,R;
int n,k;
db ans=233333333;
const db pi=acos(-1);
struct Point
{
    db x,y;
    void read()
    {
        scanf("%lf%lf",&x,&y);
    }
    Point(db _,db __):x(_),y(__){}
    Point(){}
    Point operator +(const Point &a)const{
        return Point(x+a.x,y+a.y);
    }
    Point operator -(const Point &a)const{
        return Point(x-a.x,y-a.y);
    }
    Point operator *(db a)const{
        return Point (x*a,y*a);
    }
};
db solve(db a,db b,db c)
{
    return (-b+sqrt(b*b-4*a*c))/(2*a);
}
db dot(Point &a,Point &b)
{
    return a.x*b.x+a.y*b.y;
}
db dis(Point &a)
{
    return a.x*a.x+a.y*a.y;
}
struct node
{
    Point p[105],v[105];
    db t[105];
    db get_intersec(Point &x,Point &v,Point &nx,Point &nv)
    {
        db t=solve(dis(v),2*dot(x,v),dis(x)-R*R);
        nx=x+v*t;
        db a1=atan2(v.y,v.x),a2=atan2(nx.y,nx.x);
        db a3=2*a2-a1-pi,d=sqrt(dis(v));
        nv=Point(d*cos(a3),d*sin(a3));
        return t;
    }
    void init()
    {
        p[0].read();v[0].read();
        p[0].x-=x2;p[0].y-=y2;
        for(int i=1;i<=k;i++)
            t[i]=t[i-1]+get_intersec(p[i-1],v[i-1],p[i],v[i]);
    }
}a[105]; 
db get_min(db a,db b,db c,db t)
{
    db tmp=-b/(2*a);
    tmp=min(t,tmp);tmp=max(tmp,0.0);
    return sqrt(a*tmp*tmp+b*tmp+c);
}
void update(Point x,Point v,db t)
{
    ans=min(ans,get_min(dis(v),2*dot(v,x),dis(x),t));
}
int main()
{
    cin>>x2>>y2>>R;
    cin>>n>>k;
    for(int i=1;i<=n;i++) 
    a[i].init();
    for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)
    {
        Point l1=a[i].p[0],l2=a[j].p[0];
        Point v1=a[i].v[0],v2=a[j].v[0];
        int t1=1,t2=1;
        db lt=0;
        while(t1<k&&t2<k)
        {
            if(a[i].t[t1]<a[j].t[t2])
            {
                update(l1-l2,v1-v2,a[i].t[t1]-lt);
                l1=a[i].p[t1];v1=a[i].v[t1];
                l2=l2+v2*(a[i].t[t1]-lt);
                lt=a[i].t[t1];
                t1++;
            }
            else
            {
                update(l2-l1,v2-v1,a[j].t[t2]-lt);
                l2=a[j].p[t2];v2=a[j].v[t2];
                l1=l1+v1*(a[j].t[t2]-lt);
                lt=a[j].t[t2];
                t2++;
            }
        }
    }
    printf("%.3lf\n",ans);
}```