【kuangbin专题】计算几何基础-白红宇

【kuangbin专题】计算几何基础

阅读量：6937 次

发布时间：2019-06-27

本文共 14731 字，大约阅读时间需要 49 分钟。

1.poj2318 TOYS

传送：

题意：有m个点落在n+1个区域内。问落在每个区域的个数。

分析：二分查找落在哪个区域内。叉积判断点与线段的位置。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxn=5010; 6 struct point{ 7     int x,y; 8     point(){ } 9     point(int _x,int _y):x(_x),y(_y){}10     point operator +(const point &b) const{11         return point(x+b.x,y+b.y);12     } 13     point operator -(const point &b) const{14         return point(x-b.x,y-b.y);15     }16     int operator *(const point &b) const{17         return x*b.x,y*b.y; 18     }19     int operator ^(const point &b) const{20         return x*b.y-y*b.x;21     }22 };23 struct line{24     point s,e;25     line(){}26     line(point _s,point _e):s(_s),e(_e){}27 }box[maxn];28 int xmult(point p,point a,point b){29     return (b-a)^(p-a);30 }31 int ans[maxn];32 int main(){33     ios::sync_with_stdio(false);34     cin.tie(0);cout.tie(0);35     int n,m,x1,y1,x2,y2,ui,li,x,y;36     int _=0;37     while (cin >> n >> m >> x1 >> y1 >> x2 >> y2 && n){38         if (_!=0) cout << endl;39         for (int i=0;i
         
          > ui >> li;41             box[i]=line(point(ui,y1),point(li,y2));42         }43         box[n]=line(point(x2,y1),point(x2,y2));44         memset(ans,0,sizeof(ans));45         point p;46         for (int i=0;i
          
           > x >> y;48             p=point(x,y);49             int l=0,r=n,mid,tmp;50             while (l<=r){51                 mid=(l+r)>>1;52                 if (xmult(p,box[mid].s,box[mid].e)<0){53                     tmp=mid;54                     r=mid-1;55                 }56                 else l=mid+1;57             }58             ans[tmp]++;59         }60         for (int i=0;i<=n;i++) cout << i << ": " << ans[i] << endl;61         _++;62     }63     return 0;64 }

poj2318

2.poj2398 Toy Storage

传送：

题意：与poj2318相同，输出要求输出有t（t>0）个玩具的格子数。

分析：同2318

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxn=1010; 6 struct point{ 7     int x,y; 8     point(){ } 9     point(int _x,int _y):x(_x),y(_y){}10     point operator +(const point &b) const{11         return point(x+b.x,y+b.y);12     } 13     point operator -(const point &b) const{14         return point(x-b.x,y-b.y);15     }16     int operator *(const point &b) const{17         return x*b.x,y*b.y; 18     }19     int operator ^(const point &b) const{20         return x*b.y-y*b.x;21     }22 };23 struct line{24     point s,e;25     line(){}26     line(point _s,point _e):s(_s),e(_e){}27     //28     bool operator< (const line &b) const{29         return s.x
         
          > n >> m >> x1 >> y1 >> x2 >> y2 && n){45         for (int i=0;i
          
           > ui >> li;47             box[i]=line(point(ui,y1),point(li,y2));48         }49         box[n]=line(point(x2,y1),point(x2,y2));50         sort(box,box+1+n);51         memset(ans,0,sizeof(ans));52         point p;53         for (int i=0;i
           
            > x >> y;55 p=point(x,y);56 int l=0,r=n,mid,tmp;57 while (l<=r){58 mid=(l+r)>>1;59 if (xmult(p,box[mid].s,box[mid].e)<0){60 tmp=mid;61 r=mid-1;62 }63 else l=mid+1;64 }65 ans[tmp]++;66 }67 memset(vis,0,sizeof(vis));68 for (int i=0;i<=n;i++) if (ans[i]) vis[ans[i]]++;69 cout << "Box\n"; 70 for (int i=1;i<=n;i++){71 if (!vis[i]) continue;72 cout << i << ": " << vis[i] << endl;73 }74 }75 return 0;76 }

poj2398

3.poj3304 Segments

传送：

题意：给出n条线段两个端点的坐标，问所有线段投影到一条直线上，如果这些所有投影至少相交于一点就输出Yes！，否则输出No！。

分析：如果有存在这样的直线，过投影相交区域作直线的垂线，该垂线必定与每条线段相交，问题转化为问是否存在一条线和所有线段相交。

直线肯定经过两个端点。两两枚举端点（包括同一条线段），判断直线和线段是否相交。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const double eps=1e-8; 7 const int maxn=110; 8 struct point{ 9     double x,y;10     point(){}11     point(double _x,double _y):x(_x),y(_y){}12     point operator -(const point &b) const{13         return point(x-b.x,y-b.y);14     }15     double operator ^(const point &b) const{16         return x*b.y-y*b.x;17     }18     double operator *(const point &b) const{19         return x*b.x+y*b.y;20     } 21 };22 struct line{23     point s,t;24     line(){}25     line(point _s,point _t):s(_s),t(_t){}26 }a[maxn];27 int sgn(double x){28     if (fabs(x)
          
           > t;49     double x1,x2,y1,y2;50     while (t--){51         cin >> n;52         for (int i=0;i
           
            > x1 >> y1 >> x2 >> y2;54 a[i]=line(point(x1,y1),point(x2,y2));55 }56 int f=0;57 for (int i=0;i

poj3304

4.poj1269 Intersecting Lines

传送：

题意：给出两条直线，问两条直线的位置关系（平行，重合，相交）。相交的话输出交点。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 const double eps=1e-8; 8 int sgn(double x){ 9     if (fabs(x)
           
             operator &(const line &b) const{32 point res=s;33 if (sgn((s-t)^(b.s-b.t))==0){34 if (sgn((b.s-s)^(b.t-s))==0) return make_pair(res,0); //两直线重合35 else return make_pair(res,1); //两直线平行 36 }37 double k=((s-b.s)^(b.s-b.t))/((s-t)^(b.s-b.t));38 res.x+=(t.x-s.x)*k;39 res.y+=(t.y-s.y)*k;40 return make_pair(res,2); //两直线相交 41 }42 };43 int main(){44 int n; cin >> n;45 double x1,x2,y1,y2;46 line l1,l2;47 cout << "INTERSECTING LINES OUTPUT\n"; 48 for (int i=0;i
            
             > x1 >> y1 >> x2 >> y2;50 l1=line(point(x1,y1),point(x2,y2));51 cin >> x1 >> y1 >> x2 >> y2;52 l2=line(point(x1,y1),point(x2,y2));53 pair
             
               ans=l1&l2;54 if (ans.second==2) printf("POINT %.2f %.2f\n",ans.first.x,ans.first.y);55 else if (ans.second==1) printf("NONE\n");56 else printf("LINE\n");57 }58 cout << "END OF OUTPUT\n";59 return 0;60 }

poj1269

5.poj1556 The Doors

传送：

题意：10×10的方阵内有若干个墙壁，墙壁之间有空隙（可通过），问从（0,5）到（10,5）的最短路。

分析：建图，线段两两判断是否相交，不相交就建边。然后跑最短路。（数据较小，随便最短路算法。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 const double eps=1e-8; 9 const double inf=1e20; 10 const int maxn=110; 11 double mp[maxn][maxn]; 12 int sgn(double x){ 13 if (fabs(x)
            
             = min(l2.s.x,l2.e.x) 42 && max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) 43 && max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) 44 && max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) 45 && sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=0 46 && sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=0; 47 } 48 double floyd(int n){ 49 for (int i=0;i<=n;i++) 50 for (int j=0;j<=n;j++) 51 for (int k=0;k<=n;k++) 52 if (mp[i][k]+mp[k][j]
             
              > n && n!=-1){ 58 for (int i=1;i<=n;i++){ 59 cin >> x >> y1 >> y2 >> y3 >> y4; 60 a[2*i-1]=line(point(x,y1),point(x,y2)); 61 a[2*i]=line(point(x,y3),point(x,y4)); 62 } 63 for (int i=0;i<=4*n+1;i++) 64 for (int j=0;j<=4*n+1;j++) 65 if (i==j) mp[i][j]=0;else mp[i][j]=inf; 66 for (int i=1;i<=4*n;i++){ 67 int l=(i+3)/4; 68 int f=1; 69 point tmp; 70 if (i&1) tmp=a[(i+1)/2].s; else tmp=a[(i+1)/2].e; 71 for (int j=1;j

poj1556

6.poj2653 Pick-up sticks

传送：

题意：问有多少线段不与比它编号大的相交。

分析：线段交直接暴力判断。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
            5 using namespace std; 6 const double eps=1e-8; 7 const int maxn=100010; 8 int sgn(double x){ 9     if (fabs(x)
          
           = min(l2.s.x,l2.e.x) 38         && max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x)39         && max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) 40         && max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y)41         && sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=042         && sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=0;43 }44 bool vis[maxn];45 int main(){46     ios::sync_with_stdio(false);47     cin.tie(0);cout.tie(0);48     int n; double x1,x2,y1,y2;49     while (cin >> n && n){50         for (int i=0;i
           
            > x1 >> y1 >> x2 >> y2;52 a[i]=line(point(x1,y1),point(x2,y2));53 vis[i]=1;54 }55 for (int i=0;i

poj2653

7.poj1066 Treasure Hunt

传送：

题意：在金字塔内有一个宝藏p(x,y);现在要取出这个宝藏在金字塔内有许多墙为了进入宝藏所在的房间必须把墙炸开但是炸墙只能炸每个房间墙的中点求将宝藏运出城堡所需要的最小炸墙数。

分析：枚举每个线段的端点与P点形成的直线，与多少线段相交。其次，可以从墙壁顶点进入，相交数+1与ans比较。

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 using namespace std; 7 const double dx[]={
     0,0,100,100},dy[]={
     0,100,0,100}; 8 const double eps=1e-8; 9 const int maxn=35;10 int sgn(double x){11     if (fabs(x)
            
             = min(l2.s.x,l2.e.x) 37 && max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x)38 && max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) 39 && max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y)40 && sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=041 && sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=0;42 }43 int main(){44 int n; double x1,y1,x2,y2;45 while (cin >> n){46 for (int i=1;i<=n;i++){47 cin >> x1 >> y1 >> x2 >> y2;48 a[i]=line(point(x1,y1),point(x2,y2));49 p[2*i-1]=point(x1,y1); p[2*i]=point(x2,y2);50 }51 point s;52 cin >> x1 >> y1;53 s=point(x1,y1);54 int ans=233333;55 for (int i=1;i<=2*n;i++){56 line l1=line(s,p[i]);57 int res=0;58 for (int j=1;j<=n;j++)59 if (inter(l1,a[j])) res++;60 ans=min(res,ans);61 }62 for (int i=0;i<4;i++){63 line l1=line(s,point(dx[i],dy[i]));64 int res=0;65 for (int j=1;j<=n;j++)66 if (inter(l1,a[j])) res++;67 ans=min(ans,res+1);68 }69 cout << "Number of doors = " << ans << endl;70 }71 return 0;72 }

poj1066

8.poj1410 Intersection

传送：

题意：给定一个矩阵和线段，若线段在矩阵内或与矩阵某条边相交，输出T，否则输出F。

分析：判断线段与四条边线段交。再判断是否在矩阵内。

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 using namespace std; 6 const double eps=1e-8;  7 const int maxn=10; 8 int sgn(double x){ 9     if (fabs(x)
           
            = min(l2.s.x,l2.e.x) 35         && max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x)36         && max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) 37         && max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y)38         && sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s))<=039         && sgn((l1.s-l2.s)^(l2.e-l2.s))*sgn((l1.e-l2.s)^(l2.e-l2.s))<=0;40 }41 int onseg(point p,line l){42     return 43         sgn((l.s-p)^(l.e-p))==0 && 44         sgn((p.x-l.s.x)*(p.x-l.e.x))<=0 &&45         sgn((p.y-l.s.y)*(p.y-l.e.y))<=0;46 }47 //判断点在凸多边形内48 //点形成一个凸包，而且按逆时针排序（如果是顺时针把里面的<0改为>0）49 //点的编号:0~n-150 //返回值：51 //-1:点在凸多边形外52 //0:点在凸多边形边界上53 //1:点在凸多边形内54 int inConvexPoly(point a,point p[],int n){55     for (int i=0;i
            
             > t;63 double x1,y1,x2,y2;64 while (t--){65 cin >> x1 >> y1 >> x2 >> y2;66 line l=line(point (x1,y1),point(x2,y2));67 cin >> x1 >> y1 >> x2 >> y2;68 if (x1>x2) swap(x1,x2); if (y1>y2) swap(y1,y2);69 p[0]=point(x1,y1);p[1]=point(x2,y1);p[2]=point(x2,y2);p[3]=point(x1,y2);70 if (inter(l,line(p[0],p[1])) || inter(l,line(p[1],p[2])) 71 || inter(l,line(p[2],p[3])) || inter(l,line(p[3],p[0]))){72 cout << "T\n";continue;73 }74 if (inConvexPoly(l.s,p,4)>=0 || inConvexPoly(l.e,p,4)>=0){75 cout << "T\n"; continue;76 }77 cout << "F\n";78 }79 return 0;80 }

poj1410

9.poj1696 Space Ant

传送：

题意：一只蚂蚁只会向左转，现在给出平面上很多个点，求解一种走法能使得蚂蚁能经过的点最多，每个顶点该蚂蚁只能经过一次，且所行走的路线不能发生交叉。

分析：对于题目所输入的点，先找出最左下方的顶点(即纵坐标最小的顶点)，然后对剩下的顶点按照对与左下点的极角排序，然后反复找最左下的点，反复进行极角排序，同时记录排序后左下的顶点。

极角排序方法：利用叉积，看向量p1和p2的叉积是否小于零，是则说明p1在p2逆时针方向，即p1的极角比p2的大，极角相同则按离p0距离降序排序。

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 using namespace std; 6 const double eps=1e-8; 7 const int maxn=55; 8 int sgn(double x){ 9     if (fabs(x)
           
            > t;40     double x,y;41     while (t--){42         cin >> n;43         for (int i=0;i
            
             > p[i].id >> p[i].x >> p[i].y;45 if (p[i].y

poj1696

10.poj3347 Kadj Squares

传送：

题意：给出n个边长的正方形，要求尽可能贴着放。问最后从上往下看能看到哪几个正方形。

分析：每新增一个正方形，就让他与左侧的每一个正方形贴紧，求的其左端坐标，最终结果一定是最大的那个。然后求的相应的最右端坐标。这样就转化为了线段，最后用朴素的n2算法求出每条线段没有被覆盖的长度，如果长度大于0，即可输出。

1 #include
       
         2 #include
        
          3 #include
         
           4 using namespace std; 5 const int maxn=55; 6 struct node{ 7     int len,l,r; 8 }a[maxn]; 9 int main(){10     int n;11     while (cin >> n && n){12         for (int i=0;i
          
           > a[i].len;  //将图形扩大根2倍，len为对角线长度的一半 14             a[i].l=0;15             for (int j=0;j
           
            a[j].len && a[i].l

poj3347

11.poj1654 Area

传送：

题意：从原点开始，超八个方向走。问最后形成的多边形面积。

分析：rt。直接求多边形面积。

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 using namespace std; 6 const int dx[10]={
     0,-1,0,1,-1,0,1,-1,0,1},dy[10]={
     0,-1,-1,-1,0,0,0,1,1,1}; 7 const int maxn=1000005;  8 typedef long long ll; 9 struct point{10     int x,y;11     point(){}12     point(int _x,int _y):x(_x),y(_y){}13     ll operator ^(const point &b)const{14         return x*b.y-y*b.x;15     }16 };17 struct polygon{18     int n;19     point p[maxn];20     void add(point q){p[n++]=q;}21     ll getarea(){22         ll sum=0;23         for (int i=0;i
           
            > t;31     while (t--){32         C.n=0;33         ll x=0,y=0;34         while (cin >> ch && ch!='5'){35             k=ch-'0';36             x+=dx[k]; y+=dy[k];37             C.add(point(x,y));    38         }39         ll ans=C.getarea();40         if (ans&1) cout << ans/2 << ".5\n";41         else cout << ans/2 << endl; 42     } 43     return 0;44 }

poj1654

12.poj2954 Triangle

　　传送：

　　题意：求三角形内部有多少格点。

　　分析：pick定理。S=a+b/2-1。a代表多边形内部的格点，b代表多边形边上的格点。S代表多边形面积。

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 using namespace std; 6 typedef long long ll; 7 const int maxn=5; 8 struct point{ 9     int x,y;10     point(){}11     point(int _x,int _y):x(_x),y(_y){}12     ll operator ^(const point &b)const{13         return x*b.y-y*b.x;14     }15 };16 struct polygon{17     int n;18     point p[maxn];19     void add(point q){p[n++]=q;}20     ll getarea(){21         ll sum=0;22         for (int i=0;i
           
            > x1 >> y1 >> x2 >> y2 >> x3 >> y3){34         if (!x1 && !x2 && !x3 && !y1 && !y2 && !y3) break;35         C.n=0;36         C.add(point(x1,y1));C.add(point(x2,y2));C.add(point(x3,y3));37         ll area=C.getarea();38         int b=0;39         for (int i=0;i