UVA 1398 Meteor - c++编程基础

目测佳哥书上几何那的题，今天一看才知道没那么难，一做才知道没那么简单。

判断射线是否穿过矩形，可以采用这种办法：

求出所有可行的交点，其中矩形顶点要算2次，

对交点去重，如果剩下2个点，那么是穿过的。

另外必须注意的是，如果开始点在矩形内，需要当作一个“交点”，这里是一个易错点。

其实求得交点是用时间来表示的。

那么时间小的必然是穿入点，时间大的必然是穿出点。以此作为两个事件点，一个为+1,一个为-1。

求出所有射线与矩形相交的时间后，对事件按时间排序，然后扫描一遍求出最大值即可。

另外有两个小技巧，一个是代码中的，同一时间的事件点（有这样数据）需要求和，而不能一个一个计算。

另外一个技巧就是对时间相同的事件点，按照先出后进，就可以一个一个计算。

#include
  
   
#include
   
     #include
    
      #include
      #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            using namespace std; const int X=60; const double sqt2=sqrt(0.5); const double eps=1e-8; const double pi=3.14159265358979323; struct point{ double x,y,vx,vy; point(){} point(double xx,double yy){ x=xx;y=yy; } }a; point operator +(point a,point b){ return point(a.x+b.x,a.y+b.y); } point operator -(point a,point b){ return point(a.x-b.x,a.y-b.y); } point operator *(point a,double b){ return point(a.x*b,a.y*b); } point operator /(point a,double b){ return point(a.x/b,a.y/b); } int sign(double x){ return x<-eps -1:x>eps; } bool operator <(point a,point b){ return sign(a.x-b.x)<0||sign(a.x-b.x)==0&&sign(a.y-b.y)<0; } bool operator ==(point a,point b){ return sign(a.x-b.x)==0&&sign(a.y-b.y)==0; } double det(point a,point b){ return a.x*b.y-a.y*b.x; } double dot(point a,point b){ return a.x*b.x+a.y*b.y; } double dis(point a,point b){ return sqrt(dot(a-b,a-b)); } bool on(point a,point b,point c){ return sign(a.x-max(b.x,c.x))<=0&&sign(a.x-min(b.x,c.x))>=0&& sign(a.y-max(b.y,c.y))<=0&&sign(a.y-min(b.y,c.y))>=0; } struct event{ double t; int sign; }e[1000100]; double w,h; int top; bool in(double x,double y){ return sign(x)>0&&sign(x-w)<0&&sign(y)>0&&sign(y-h)<0; } void solve(point a){ double t,x,y,tmp[10]; int k=0; if(sign(a.vx)){ t=-a.x/a.vx; y=a.y+a.vy*t; if(sign(t)>=0&&sign(y)>=0&&sign(y-h)<=0) tmp[k++]=t; t=(w-a.x)/a.vx; y=a.y+a.vy*t; if(sign(t)>=0&&sign(y)>=0&&sign(y-h)<=0) tmp[k++]=t; } if(sign(a.vy)){ t=-a.y/a.vy; x=a.x+a.vx*t; if(sign(t)>=0&&sign(x)>=0&&sign(x-w)<=0) tmp[k++]=t; t=(h-a.y)/a.vy; x=a.x+a.vx*t; if(sign(t)>=0&&sign(x)>=0&&sign(x-w)<=0) tmp[k++]=t; } if(in(a.x,a.y))tmp[k++]=0.0; sort(tmp,tmp+k); k=unique(tmp,tmp+k)-tmp; if(k==2&&in(a.x+a.vx*(tmp[0]+tmp[1])/2,a.y+a.vy*(tmp[0]+tmp[1])/2)){ e[top].t=tmp[0]; e[top++].sign=1; e[top].t=tmp[1]; e[top++].sign=-1; } } bool cmp(event a,event b){ return a.t