题目大意：给定一个圆，一堆粒子在里面反射，每个粒子只能撞墙k次，，求全程粒子间距离的最小值
每两个粒子之间计算一遍
反射就是把射线沿着切线作镜像变换
随便搞搞咯……
#include <cmath>#include <cstdio>#include <cstring>#include <iomanip>#include <iostream>#include <algorithm>#define M 110#define EPS 1e-7#define INF 1e9using namespace std;typedef long double ld;struct Point{ld x,y;Point() {}Point(ld _,ld __):x(_),y(__) {}friend istream& operator >> (istream &_,Point &p){_>>p.x>>p.y;return _;}friend Point operator + (const Point &p1,const Point &p2){return Point(p1.x+p2.x,p1.y+p2.y);}friend Point operator – (const Point &p1,const Point &p2){return Point(p1.x-p2.x,p1.y-p2.y);}friend ld operator * (const Point &p1,const Point &p2){return p1.x*p2.y-p1.y*p2.x;}friend Point operator * (const Point &p,ld rate){return Point(p.x*rate,p.y*rate);}friend ld Distance(const Point &p1,const Point &p2){return sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) );}}O;struct Line{Point p,v;Line() {}Line(const Point &_,const Point &__):p(_),v(__) {}friend istream& operator >> (istream &_,Line &l){cin>>l.p>>l.v;return _;}friend Point Get_Intersection(const Line &l1,const Line &l2)//计算两条直线的交点{Point u=l1.p-l2.p;ld temp=(l2.v*u)/(l1.v*l2.v);return l1.p+l1.v*temp;}}a[M][M];int n,k;ld r,ans=INF;ld t[M][M];ld Quadratic_Equation(ld a,ld b,ld c)//解一元二次方程{ld re1=( -b+sqrt(b*b-4*a*c) )/2/a;ld re2=( -b-sqrt(b*b-4*a*c) )/2/a;return max(re1,re2);}ld Get_Intersection(const Line &l)//计算直线与圆的交点{return Quadratic_Equation(l.v.x*l.v.x+l.v.y*l.v.y,2*(l.p.x*l.v.x+l.p.y*l.v.y),l.p.x*l.p.x+l.p.y*l.p.y-r*r );}Point Mirror(const Point &p,const Line &l)//求点p关于直线l的镜像{Point u=Point(l.v.y,-l.v.x);Point intersection=Get_Intersection(Line(p,u),l);return intersection+(intersection-p);}ld Min_Distance(const Line &l1,const Line &l2,ld l,ld r){ld a=(l1.v.x-l2.v.x)*(l1.v.x-l2.v.x)+(l1.v.y-l2.v.y)*(l1.v.y-l2.v.y);ld b=(l1.p.x-l2.p.x)*(l1.v.x-l2.v.x)+(l1.p.y-l2.p.y)*(l1.v.y-l2.v.y);if(a<EPS) return Distance(l1.p+l1.v*r,l2.p+l2.v*r);ld t=-b/a;if(t>r) t=r;if(t<l) t=l;return Distance(l1.p+l1.v*t,l2.p+l2.v*t);}void Calculate(int x,int y){int i=1,j=1;ld last=0;while(i<=k&&j<=k){if(t[x][i]>t[y][j])swap(x,y),swap(i,j);ans=min(ans,Min_Distance(a[x][i],a[y][j],last,t[x][i]) );last=t[x][i];i++;}}int main(){int i,j;cin>>O>>r>>n>>k;for(i=1;i<=n;i++){cin>>a[i][1];a[i][1].p=a[i][1].p-O;for(j=2;j<=k;j++){t[i][j-1]=Get_Intersection(a[i][j-1]);Point intersection=a[i][j-1].p+a[i][j-1].v*t[i][j-1];Point intersection_T=Point(intersection.y,-intersection.x);a[i][j]=Line( Mirror(a[i][j-1].p,Line(intersection,intersection_T)) ,Mirror(a[i][j-1].v,Line(Point(0,0),intersection_T)) ) ;}t[i][k]=Get_Intersection(a[i][k]);}for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)Calculate(i,j);cout<<fixed<<setprecision(3)<<ans<<endl;return 0;}
感受不同地域不一样的节奏与表象。
