首页 > 代码库 > 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 }
BZOJ2618 [Cqoi2006]凸多边形
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。