bzoj 2618[Cqoi2006]凸多边形

2618: [Cqoi2006]凸多边形

Time Limit: 5 Sec Memory Limit: 128 MB

Description

逆时针给出n个凸多边形的顶点坐标，求它们交的面积。例如n=2时，两个凸多边形如下图：

则相交部分的面积为5.233。

Input

第一行有一个整数n，表示凸多边形的个数，以下依次描述各个多边形。第i个多边形的第一行包含一个整数m_i，表示多边形的边数，以下m_i行每行两个整数，逆时针给出各个顶点的坐标。

Output

输出文件仅包含一个实数，表示相交部分的面积，保留三位小数。

Sample Input

2
6
-2 0
-1 -2
1 -2
2 0
1 2
-1 2
4
0 -3
1 -1
2 2
-1 0

Sample Output

5.233

HINT

100%的数据满足：2<=n<=10，3<=m_i<=50，每维坐标为[-1000,1000]内的整数

一道练习半平面交的好题

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #define LL long long 
  7 
  8 using namespace std;
  9 
 10 const int MAXN = 10000;
 11 const double eps = 1e-6;
 12 int N, m;
 13 int tot = 0;
 14 int head, tail;
 15 int s[MAXN];
 16 
 17 inline LL read()
 18 {
 19     LL x = 0, w = 1; char ch = 0;
 20     while(ch < '0' || ch > '9') {
 21         if(ch == '-') {
 22             w = -1;
 23         }
 24         ch = getchar();
 25     }
 26     while(ch >= '0' && ch <= '9') {
 27         x = x * 10 + ch - '0';
 28         ch = getchar();
 29     }
 30     return x * w;
 31 }
 32 
 33 struct Point {
 34     double x, y;
 35 } p[MAXN], n[MAXN];
 36 
 37 struct Line {
 38     Point p, v;
 39     double k;
 40 } l[MAXN], tmp[MAXN];
 41 
 42 Point operator *(Point a, double k)
 43 {
 44     Point t;
 45     t = a;
 46     t.x *= k ,t.y *= k;
 47     return t;
 48 }
 49 
 50 double operator ^(Point a, Point b)
 51 {
 52     return a.x * b.y - a.y * b.x;        
 53 }
 54 
 55 Point operator +(Point a, Point b)
 56 {
 57     Point t;
 58     t.x = a.x + b.x, t.y = a.y + b.y;
 59     return t;    
 60 }
 61 
 62 Point operator -(Point a, Point b)
 63 {
 64     Point t;
 65     t.x = a.x - b.x, t.y = a.y - b.y;
 66     return t;        
 67 }
 68 
 69 Point inter(Line a, Line b)
 70 {
 71     Point t, u;
 72     double S1, S2;
 73     u = b.p - a.p;
 74     S1 = u ^ a.v, S2 = a.v ^ b.v;
 75     t = b.p + b.v * (S1 / S2);
 76     return t;
 77 }
 78 
 79 int sign(double x)
 80 {
 81     double d = fabs(x);
 82     if(d <= eps) {
 83         return 0;
 84     } else if(x > 0) {
 85         return 1;
 86     } else {
 87         return -1;
 88     }
 89 }
 90 
 91 bool judge(Point p, Line a)
 92 {
 93     //cout<<p.x<<" "<<p.y<<endl;
 94     Point u = p - a.p, v = a.v;
 95 //    cout<<u.x<<" "<<u.y<<" "<<v.x<<" "<<v.y<<endl; 
 96 //    cout<<(u ^ v)<<endl;
 97     if(sign(u ^ v) >= 0) {
 98         return true;
 99     }
100     return false;
101 }
102 
103 bool cmp(Line a, Line b)
104 {
105     if(a.k == b.k) {
106         if(judge(a.p, b)) {
107             return false;
108         } else {
109             return true;
110         }
111     }
112     return a.k < b.k;
113 }
114 
115 void work()
116 {
117     head = 0, tail = 0;
118     for(int i = 1; i <= tot; i++) {
119         Point p = inter(l[s[head]], l[s[head + 1]]);
120         int x = s[head], y = s[head + 1];
121     //    cout<<s[head]<<" "<<s[head + 1]<<" "<<p.x<<" "<<p.y<<endl;
122     //    cout<<l[x].p.x<<" "<<l[x].p.y<<" "<<l[x].v.x<<" "<<l[x].v.y<<endl;
123     //    cout<<l[y].p.x<<" "<<l[y].p.y<<" "<<l[y].v.x<<" "<<l[y].v.y<<endl;
124         //cout<<p.x<<" "<<p.y<<endl;
125         while(tail > head + 1 && judge(inter(l[s[tail - 1]], l[s[tail - 2]]), l[i])) {
126             tail--;
127         }
128         while((head + 1 < tail) && judge(inter(l[s[head]], l[s[head + 1]]), l[i])) {    
129             head++;
130         }
131         s[tail++] = i;
132     }
133     while(tail > head + 1 && judge(inter(l[s[tail - 1]], l[s[tail - 2]]), l[s[head]])) {
134         tail--;
135     }
136     /*while(tail > head + 1 && judge(inter(l[s[head]], l[s[head + 1]]), l[tail - 1])) {
137         head++;
138     }
139     /*for(int i = head; i < tail; i++) {
140         cout<<l[s[i]].k<<" ";
141     }
142     cout<<endl;*/
143     double ans = 0;
144     int cnt = 0;
145     for(int i = head; i < tail - 1; i++) {
146         n[++cnt] = inter(l[s[i]], l[s[i + 1]]);
147     }
148     n[++cnt] = inter(l[s[tail - 1]], l[s[head]]);
149     if(cnt == 0 || cnt == 1) {
150         printf("0.000
");
151         return;
152     } 
153     for(int i = 1; i <= cnt; i++) {
154         ans += n[i] ^ n[i % cnt + 1];
155     }
156 //    cout<<ans<<endl; 
157     ans = ans / 2;
158     printf("%.3lf
", ans);
159 }
160 
161 int main()
162 {
163     N = read();
164     for(int i = 1; i <= N; i++) {
165         m = read();
166         for(int i = 1; i <= m; i++) {
167             p[i].x = read(), p[i].y = read();
168         }
169         for(int i = 1; i <= m; i++) {
170             l[++tot].p = p[i];
171             l[tot].v = p[i % m + 1] - p[i];
172             l[tot].k = atan2(l[tot].v.y, l[tot].v.x);
173         //    cout<<l[tot].k<<" "<<" "<<l[tot].p.x<<" "<<l[tot].p.y<<endl;;
174         }
175         //cout<<endl;
176     }
177     sort(l + 1, l + tot + 1, cmp);
178     int cnt = tot;
179     tot = 0;
180     for(int i = 1; i <= cnt; i++) {
181         if(l[i].k != l[i - 1].k || i == 1) {
182             tmp[++tot] = l[i];
183         }
184     }
185     for(int i = 1; i <= tot; i++) {
186         l[i] = tmp[i];
187     }
188     /*for(int i = 1; i <= tot; i++) {
189         cout<<l[i].k<<" ";
190     }
191     cout<<endl;*/
192     work();
193 }

View Code