扫除技术提供了对一组几何物体进行排序的方法

动态数据结构

线段端点每遇到一个端点就检查该点是否是相交点

我们简化问题提出两种假设：这在之后证明计算几何的正确性提供了简化

= == = == == = == = = = = == = = == = == = == == = = == == = == = == = = = =

//ccw函数的顺／逆时针的原理

//stl的complex类

计算几何基础：求线段是否相交，特定线段相交

算法导论的实现。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5   6 using namespace std;  7 #define maxn 15  8 #define eps 1e-10  9  10 double add(double a,double b) 11 { 12     if(abs(a+b)
          
           0 && d2<0)||(d1<0 && d2>0)) && ((d3>0 && d4<0)|| (d3<0 && d4>0))) 67         return true; 68     else if(d1==0 && on_segment(p2,q2,p1)) 69         return true; 70     else if(d2==0 && on_segment(p2,q2,q1)) 71         return true; 72     else if(d3==0 && on_segment(p1,q1,p2)) 73         return true; 74     else if(d4==0 && on_segment(p1,q1,q2)) 75         return true; 76     else return false; 77 } 78  79  80 node p[maxn],q[maxn]; 81  82 int main() 83 {
    //效率高＝ ＝ O(1) 84     int n,m; 85     int a,b; 86     scanf("%d",&n); 87     for(int i=0;i
          
         
        
       
      

 

极限情况考虑，物体撞击。

1.考虑直接撞上猪，然后在撞上的同时，猪上方的障碍物要保证不相撞。在这条路线中途也不能装上其他的障碍物，考虑以这条路径去走的，在走到某个障碍物时考虑与左侧和右侧的相对位置，然后做判断。

2.考虑不直接撞上猪，在飞的过程中以每个障碍物的左上角或者右上角为极限情况考虑然后考虑在这个飞行过程中到达猪x位置时，y是否大于它，且中途不再撞到障碍物。//???＝ ＝。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 using namespace std; 8  9 #define eps 1e-1010 #define maxn 5511 12 const double g=9.8;13 14 int N,V,X,Y;15 int L[maxn],B[maxn],R[maxn],T[maxn];16 17 18 double calc(double vy,double t)19 {20     return vy*t-g*t*t/2;21 }22 23 int cmp(double lb,double ub,double a)24 {25     return a
           
             ub-eps ? 1:0;26 }27 28 bool check(double qx,double qy)29 {30 double a=g*g/4,b=g*qy-V*V,c=qx*qx+qy*qy;31 32 double D=b*b-4*a*c;33 34 if(D<0 && D>-eps) D=0;35 if(D<0) return false;36 37 for(int d=-1;d<=1;d+=2)38 {39 double t2=(-b+d*sqrt(D))/(2*a);40 if(t2<=0) continue;41 double t=sqrt(t2);42 43 double vx=qx/t,vy=(qy+g*t*t/2)/t;44 45 double yt=calc(vy,X/vx);46 if(yt
            
             =X) continue;52 53 if(R[i]==X && Y<=T[i] && B[i]<=yt) ok=false;54 55 int yL=cmp(B[i],T[i],calc(vy,L[i]/vx));56 int yR=cmp(B[i],T[i],calc(vy,R[i]/vx));57 int xH=cmp(L[i],R[i],vx*(vy/g));58 int yH=cmp(B[i],T[i],calc(vy,vy/g));59 if(xH==0 && yH>=0 && yL<0) ok=false;60 if(yL*yR<=0) ok=false;61 }62 if(ok) return true;63 }64 return false;65 }66 67 void solve()68 {69 for(int i=0;i
            
           
          
         
        
       
      

 

 

uva,191

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5   6 using namespace std;  7 #define eps 1e-10  8   9 double add(double a,double b) 10 { 11     if(fabs(a+b)
          
           0 && d2<0)||(d1<0 && d2>0)) && ((d3>0 && d4<0) || (d3<0 && d4>0))) 60         return true; 61     else if(d1==0 && on_segment(p3,p4,p1)) 62         return true; 63     else if(d2==0 && on_segment(p3,p4,p2)) 64         return true; 65     else if(d3==0 && on_segment(p1,p2,p3)) 66         return true; 67     else if(d4==0 && on_segment(p1,p2,p4)) 68         return true; 69     else return false; 70 } 71  72 bool isinside(node p1,node p2,node p3) 73 { 74     return (p2.x<=p1.x)&&(p2.y>=p1.y)&&(p3.x>=p1.x)&&(p3.y<=p1.y); 75 } 76  77 int main() 78 {
    //方法不错，但是一开始可能那个赋值的算法可能有点错误。 79     int n; 80     node a,b,c,d,e,f; 81     while(~scanf("%d",&n)) 82     while(n--) 83     {
    //考虑精度，lf能很好的保证精度的缺失。 84         scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y); 85         scanf("%lf%lf%lf%lf",&e.x,&e.y,&f.x,&f.y); 86 //很明确的说明了左上角 87 //很明确的说明了右下角。然后建立线段。 88         c=node(min(e.x,f.x),max(e.y,f.y)); 89         d=node(max(e.x,f.x),min(e.y,f.y)); 90         if(segment_intersect(a,b,c,node(c.x,d.y)) || segment_intersect(a,b,node(c.x,d.y),d)|| 91            segment_intersect(a,b,c,node(d.x,c.y)) || segment_intersect(a,b,node(d.x,c.y),d)) 92         { 93             printf("T\n"); 94         } 95         else if(isinside(a,c,d) || isinside(b,c,d)) 96         { 97             printf("T\n"); 98         } 99         else printf("F\n");100     }101     return 0;102     103 }
          
         
        
       
      

uva,11343

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5   6 using namespace std;  7 #define eps 1e-10  8   9 double add(double a,double b) 10 { 11     if(fabs(a+b)
          
           0 && d2<0)||(d1<0 && d2>0)) && ((d3>0 && d4<0) || (d3<0 && d4>0))) 60         return true; 61     else if(d1==0 && on_segment(p3,p4,p1)) 62         return true; 63     else if(d2==0 && on_segment(p3,p4,p2)) 64         return true; 65     else if(d3==0 && on_segment(p1,p2,p3)) 66         return true; 67     else if(d4==0 && on_segment(p1,p2,p4)) 68         return true; 69     else return false; 70 } 71  72  73 int main() 74 { 75     node p[105],q[105]; 76     int n,m; 77     scanf("%d",&n); 78     while(n--) 79     { 80         scanf("%d",&m); 81         for(int i=0;i
          
         
        
       
      

 uva,378

有时候不需要其他的方法其实你知道的就能做，只是注意精度

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5  6 using namespace std; 7 #define eps 1e-10 8 int flag; 9 10 double add(double a,double b)11 {12     if(fabs(a+b)
         
        
       
      

 uva,10902

注意到n很大了，如果用每次输入就与前面的所有数比较为O(n*n)的复杂度，肯定超时了。

因为有最上面的管子不会超过1000个这个可以枚举，而且从逆向来看的话又能大大削减复杂度，最后弄一个二分查找，时间复杂度O(n*logn)最坏，有些情况下可能找很少的管子就可以了。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5   6 using namespace std;  7 #define eps 1e-10  8 #define maxn 100005  9  10 double add(double a,double b) 11 { 12     if(fabs(a+b)
          
           0 && d2<0)||(d1<0 && d2>0)) && ((d3>0 && d4<0) || (d3<0 && d4>0))) 62         return true; 63     else if(d1==0 && on_segment(p3,p4,p1)) 64         return true; 65     else if(d2==0 && on_segment(p3,p4,p2)) 66         return true; 67     else if(d3==0 && on_segment(p1,p2,p3)) 68         return true; 69     else if(d4==0 && on_segment(p1,p2,p4)) 70         return true; 71     else return false; 72 } 73 node p[maxn],q[maxn]; 74 int flag1; 75  76 void find(int s,int l,int r) 77 { 78     if(l>=r || flag1) return; 79     if(segment_intersect(p[s],q[s],p[l],q[l]) || segment_intersect(p[s],q[s],p[r],q[r])) 80         flag1=1; 81     find(s,l,(l+r)/2); 82     find(s,((l+r)/2)+1,r); 83 } 84  85 int main() 86 { 87     int n; 88     while(scanf("%d",&n),n) 89     { 90         int cnt=1; 91         for(int i=0;i
           
            =0 && cnt<=1000;i--) 98 { 99 flag1=0;100 find(i,i+1,n-1);101 if(segment_intersect(p[i],q[i],p[n-1],q[n-1]))102 flag1=1;103 if(flag1)104 p[i].state=0;105 else cnt++;106 }107 int flag=0;108 printf("Top sticks:");109 for(int i=0;i