LA3263计算几何+欧拉定理的应用+线段交判边

  1 /*LA3263计算几何+欧拉定理的应用+线段交判边
  2 欧拉定理:顶点+边数-面数=2
  3 思路:先找到枚举的范围，减少判断的集合，再筛选。
  4 巧妙之处：线段间产生的点如果被夹在原先定点的连线上，则产生一条新的边
  5 易错处：
  6 1、给出的第一个点和最后一个点是重合的，所以最终有n-1个初始点
  7 2、应该统一所有的点，在去重，因为新增点可能和给定点相同
  8 3、结构体重载== 时注意精度处理
  9 */
 10 #include <stdio.h>
 11 #include <stdlib.h>
 12 #include <string.h>
 13 #include <math.h>
 14 #include <ctype.h>
 15 #include <string>
 16 #include <iostream>
 17 #include <sstream>
 18 #include <vector>
 19 #include <queue>
 20 #include <stack>
 21 #include <map>
 22 #include <list>
 23 #include <set>
 24 #include <algorithm>
 25 #define INF 0x3f3f3f3f
 26 #define LL long long
 27 #define eps 1e-7
 28 using namespace std;
 29 
 30 struct Point
 31 {
 32     double x,y;
 33     Point(double x=0,double y=0):x(x),y(y){}
 34 };
 35 typedef Point Vector;
 36 int dcmp(double x)
 37 {
 38     if(fabs(x) < eps)return 0;
 39     else return x < 0 ? -1 : 1;
 40 }
 41 bool operator < (const Point &a, const Point &b)
 42 {
 43     return a.x < b.x || (a.x == b.x && a.y < b.y);
 44 }
 45 bool operator == (const Point& a, const Point &b)
 46 {
 47     return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
 48 }
 49 
 50 Vector operator-(Point A,Point B)//表示A指向B
 51 {
 52     return Vector(A.x-B.x,A.y-B.y);
 53 }
 54 Vector operator*(Vector A,double k)
 55 {
 56     return Vector(A.x*k,A.y*k);
 57 }
 58 Vector operator+(Point A,Point B)//表示A指向B
 59 {
 60     return Vector(B.x+A.x,B.y+A.y);
 61 }
 62 
 63 double Dot(Vector A,Vector B)
 64 {
 65     return A.x*B.x+A.y*B.y;
 66 }
 67 double Length(Vector A)
 68 {
 69     return sqrt(Dot(A,A));
 70 }
 71 double Angle(Vector A,Vector B)
 72 {
 73     return fabs(acos(Dot(A,B)/Length(A)/Length(B)));
 74 }
 75 double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
 76 double Area(Point A,Point B,Point C)//三角形面积
 77 {
 78     return  Cross(B-A,C-A)/2;
 79 }
 80 bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2)
 81 {
 82     double c1 = Cross(a2-a1,b1-a1), c2 = Cross(a2-a1, b2-a1);
 83     double c3 = Cross(b2-b1,a1-b1), c4 = Cross(b2-b1, a2-b1);
 84     return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
 85 }
 86 Point GetLineIntersection(Point P, Vector v, Point Q, Vector w)
 87 {
 88     Vector u = P-Q;
 89     double t = Cross(w, u) / Cross(v, w);
 90     return P+v*t;//在精度要求极高的情况下，可以考虑自定义分数类
 91 }
 92 bool OnSegment(Point p, Point a1, Point a2)
 93 {
 94     return dcmp(Cross(a1-p, a2-p))==0 && dcmp(Dot(a1 - p ,a2 - p) < 0);//含端点就是<=0
 95 }
 96 int n,cas=0;
 97 vector<Point>P;
 98 vector<Point>np;
 99 int main()
100 {//欧拉公式：顶点+边数-面数=2
101     while(cin>>n && n)
102     {
103         cas++;
104         P.clear();
105         np.clear();
106         for(int i=0;i<n;i++)
107         {
108             int x,y;
109             cin>>x>>y;
110             P.push_back(Point(x,y));
111             np.push_back(Point(x,y));//把给定点也加入的原因是：后来的连线也可能穿过给定的点。容易犯错！
112         }
113         n--;//这是一个坑，因为第一个和最后一个点相同
114         int v,e=n;//v是输入的顶点，e是在被分割前一定有n条边
115         for(int i=0;i<n;i++)
116         for(int j=i+1;j<n;j++)
117         {
118             if (SegmentProperIntersection(P[i],P[i+1],P[j],P[j+1]))//暴力枚举线段相交
119             {
120                 np.push_back(GetLineIntersection(P[i],P[i+1]-P[i],P[j],P[j+1]-P[j]));
121             }
122         }
123         sort(np.begin(),np.end());
124         int cnt=unique(np.begin(),np.end())-np.begin();
125         v=cnt;
126         for(int i=0;i<cnt;i++)//枚举每个新的点是否分割一条原来的线段，实际上，多次枚举的原因是去除多线共点的问题，不然就可以直接用数量计算出来
127         {
128             for(int j=0;j<n;j++)//注意原先线段必然是连续的点构成
129             {
130                 if ( OnSegment(np[i], P[j], P[j+1] ) ) e++;//点在线段上但不在端点上
131             }
132         }
133         printf("Case %d: There are %d pieces.
",cas,e+2-v);
134     }
135     return 0;
136 }