半平面交

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstdio>
 6 #include<vector>
 7 using namespace std;
 8 const double inf = 1e12;
 9 const double pi = acos(-1.0);
10 const double eps = 1e-8;
11 int sgn(double x){
12     if(fabs(x)<eps) return 0;
13     return x<0 ? -1 : 1;
14 }
15 struct Point{
16     double x,y;
17     Point(){}
18     Point(double x,  double y):x(x),y(y){}
19     Point operator + (Point b) {return Point(x+b.x,y+b.y); }
20     Point operator - (Point b) {return Point(x-b.x,y-b.y); }
21     Point operator * (double k) {return Point(x*k,y*k); }
22 };
23 typedef Point Vector;
24 double Cross(Vector A , Vector B){ return A.x*B.y-A.y*B.x; }
25 struct Line{
26     Point p;
27     Vector v;
28     double ang;
29     Line(){}
30     Line(Point p , Vector v):p(p),v(v){ang=atan2(v.y,v.x);}
31     bool operator < (Line &L){return ang<L.ang; } // 用于极角排序
32 };
33 // 点p在线L的左边，即点p在线L的外面
34 bool OnLeft(Line L, Point p){ return sgn(Cross(L.v,p-L.p))>0; }
35 // 两直线交点
36 Point Cross_point(Line a , Line b){
37     Vector u = a.p-b.p;
38     double t = Cross(b.v , u) / Cross(a.v , b.v);
39     return a.p+a.v*t;
40 }
41 vector<Point> HPI(vector<Line> L){
42     int n = L.size();
43     sort(L.begin() , L.end());
44     int first,last;             //指向双端队列的第一个和最后一个元素
45     vector<Point> p(n);         //两个相邻半平面的交点
46     vector<Line> q(n);         //双端队列
47     vector<Point> ans;          //半平面交形成的凸包
48     q[first=last=0] = L[0];
49     for(int i = 1; i < n; i++){
50         // 删除尾部的半平面
51         while(first<last && !OnLeft(L[i] , p[last-1])) last--;
52         // 删除首部的半平面
53         while(first<last && !OnLeft(L[i] , p[first])) first++;
54         q[++last]=L[i];         // 将当前的半平面加入到双端队列中去
55         // 极角相同，保留左边
56         if(fabs(Cross(q[last].v,q[last-1].v))<eps){
57             last--;
58             if(OnLeft(q[last],L[i].p)) q[last]=L[i];
59         }
60         if(first<last) p[last-1]=Cross_point(q[last-1] , q[last]);
61     }
62     // 删除队列中无用的半平面
63     while(first<last && !OnLeft(q[first],p[last-1])) last--;
64     if(last-first<=1) return ans; // 空集
65     p[last] = Cross_point(q[last] , q[first]);
66     for(int i = first; i <= last; i++) ans.push_back(p[i]);
67     return ans;
68 }
69 int main()
70 {
71     int T , n;
72     scanf("%d",&T);
73     while(T--){
74         scanf("%d",&n);
75         vector<Line> L;
76         L.push_back(Line(Point(0,0),Vector(0,-1)));     // 加一个半平面F:反向y轴
77         L.push_back(Line(Point(0,inf),Vector(-1,0)));   // 加一个半平面E:y极大向左的直线
78         while(n--){
79             double a,b;
80             scanf("%lf%lf",&a,&b);
81             L.push_back(Line(Point(0,a) , Vector(1,b)));
82         }
83         vector<Point> ans = HPI(L);
84         printf("%d\n",ans.size()-2); // 去掉人为加入的两个点
85     }
86     return 0;
87 }