首页 > 代码库 > BZOJ2618 [Cqoi2006]凸多边形

BZOJ2618 [Cqoi2006]凸多边形

那个叫啥,半平面交。。。

第一次写于是只能按照惯例,orz hzwer去~~~

把一个凸多边形搞成好多条线段,于是题目就变成了一堆线段的半平面交。。。

怎么感觉比仙人掌还简单一点的说。。。就是有点长

 

  1 /**************************************************************  2     Problem: 2618  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:0 ms  7     Memory:932 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13   14 using namespace std; 15 typedef double lf; 16 const int N = 1005; 17 struct Point{ 18     lf x, y; 19     Point(void){} 20     Point(lf a, lf b) : x(a), y(b){} 21 }p[N], a[N]; 22   23 struct Line{ 24     Point a, b; 25     lf slope; 26     Line(void){} 27     Line(Point x, Point y, lf z) : a(x), b(y), slope(z){} 28 }l[N], q[N]; 29 int n, cnt, tot, num; 30 lf ans; 31   32 inline int read(){ 33     int x = 0, sgn = 1; 34     char ch = getchar(); 35     while (ch < 0 || ch > 9){ 36         if (ch == -) sgn = -1; 37         ch = getchar(); 38     } 39     while (ch >= 0 && ch <= 9){ 40         x = x * 10 + ch - 0; 41         ch = getchar(); 42     } 43     return sgn * x; 44 } 45   46 inline lf operator * (const Point a, const Point b){ 47     return a.x * b.y - a.y * b.x; 48 } 49   50 inline Point operator - (const Point a, const Point b){ 51     return Point(a.x - b.x, a.y - b.y); 52 } 53   54 inline bool operator < (const Line a, const Line b){ 55     return a.slope == b.slope ? (a.b - a.a) * (b.b - a.a) > 0 : a.slope < b.slope; 56 } 57   58 inline Point inter(const Line a, const Line b){ 59     lf k1, k2, tmp; 60     Point res; 61     k1 = (b.b - a.a) * (a.b - a.a); 62     k2 = (a.b - a.a) * (b.a - a.a); 63     tmp = k1 / (k1 + k2); 64     res = Point(b.b.x + tmp *(b.a.x - b.b.x), b.b.y + tmp * (b.a.y - b.b.y)); 65     return res; 66 } 67   68 inline bool check(const Line a, const Line b, const Line t){ 69     Point p = inter(a, b); 70     return (t.b - t.a) * (p - t.a) < 0; 71 } 72   73 void work(){ 74     sort(l + 1, l + cnt + 1); 75     int L = 1, R = 2; 76     tot = 0; 77     for (int i = 1; i <= cnt; ++i){ 78         if (l[i].slope != l[i -1].slope) ++tot; 79         l[tot] = l[i]; 80     } 81   82     cnt = tot, tot = 0; 83     q[1] = l[1], q[2] = l[2]; 84     for (int i = 3; i <= cnt; ++i){ 85         while (L < R && check(q[R - 1], q[R], l[i])) --R; 86         while (L < R && check(q[L + 1], q[L], l[i])) ++L; 87         q[++R] = l[i]; 88     } 89     while (L < R && check(q[R - 1], q[R], q[L])) --R; 90     while (L < R && check(q[L + 1], q[L], q[R])) ++L; 91     q[R + 1] = q[L]; 92     for (int i = L; i <= R; ++i) 93         a[++tot] = inter(q[i], q[i + 1]); 94 } 95   96 void get_ans(){ 97     ans = 0; 98     if (tot < 3) return; 99     a[++tot] = a[1];100     for (int i = 1; i <= tot; ++i)101         ans += a[i] * a[i + 1];102     ans = fabs(ans) / 2;103 }104  105 int main(){106     n = read();107     int X, Y;108     for (int i = 1; i <= n; ++i){109         num = read();110         for (int j = 1; j <= num; ++j){111             X = read(), Y = read();112             p[j] = Point(X, Y);113         }114         p[num + 1] = p[1];115         for (int j = 1; j <= num; ++j)116             l[++cnt] = Line(p[j], p[j + 1], 0);117     }118     for (int i = 1; i <= cnt; ++i)119         l[i].slope = atan2(l[i].b.y - l[i].a.y, l[i].b.x - l[i].a.x);120     work();121     get_ans();122     printf("%.3lf\n", ans);123     return 0;124 }
View Code

 

BZOJ2618 [Cqoi2006]凸多边形