Rockdu's Blog

题目描述

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

则相交部分的面积为5.233。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

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

5.233

说明

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

半平面交裸题，基本思路就是不断加入直线不断从前后弹出直线，在操作过程中收缩答案，具体可以看这篇博客：（讲解附带图片）点我

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 1e5 + 5;
namespace G2D {
    #define T double
    #define eps 1e-10
    struct P {T x, y;P(T _x, T _y):x(_x), y(_y){}P(){}};
    inline int sg(T a) {return (a > -eps) - (a < eps);}
    bool cmp_x(const P &A, const P &B) {return A.x == B.x ? A.y < B.y : A.x < B.x;}
    inline P operator +(const P &A, const P &B) {return P(A.x + B.x, A.y + B.y);}
    inline P operator -(const P &A, const P &B) {return P(A.x - B.x, A.y - B.y);}
    inline P operator -(const P &A) {return P(-A.x, -A.y);}
    inline T operator *(const P &A, const P &B) {return A.x * B.y - B.x * A.y;}
    inline P operator *(const T &A, const P &B) {return P(A * B.x, A * B.y);}
    inline int AOnLeft(const P &A, const P &B) {return sg(B * A);} /*不要乘反，右手定则*/
    inline int AOnLeft(const P &A, const P &s, const P &t) {return sg((s - A) * (t - A));} /*不要乘反，右手定则*/
    inline T Gdis(const P &A, const P &B) {return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));}
    struct Line {
        P s, t; double a;Line(){}
        Line(P _s, P _t):s(_s), t(_t){a = atan2((_t - _s).x, (_t - _s).y);}
    }q[maxn << 1];
    inline bool operator <(const Line &A, const Line &B) {return A.a < B.a;}
    inline P Itsec(const Line &A, const Line &B) {
        T s1 = ((B.t - A.s) * (B.s - A.s)), s2 = ((B.s - A.t) * (B.t - A.t));
        return (s1 / (s1 + s2)) * (A.t - A.s) + A.s;
    }
    inline T GetArea(P * c, int cnt) {
    	T ans = 0;
    	for(register int i = 1; i < cnt; ++i)
    		ans += (c[i] - c[0]) * (c[i + 1] - c[0]);
    	return -ans;
    }
    void GetConvex(P * c, int & cnt, P * pset, int size) {
        sort(pset + 1, pset + size + 1, cmp_x);
        cnt = 0, c[++cnt] = pset[1], c[++cnt] = pset[2];
        for(register int i = 3; i <= size; ++i) {
            while(cnt > 1 && AOnLeft(pset[i] - c[cnt], c[cnt] - c[cnt - 1]) <= 0) --cnt;
            c[++cnt] = pset[i];
        }/*记得限制不能返回去*/ 
        int k = cnt;
        for(register int i = size - 1; i >= 1; --i) {
            while(cnt > k && AOnLeft(pset[i] - c[cnt], c[cnt] - c[cnt - 1]) <= 0) --cnt;
            c[++cnt] = pset[i];
        }
    }
    bool HPI(Line * lset, int size, P * convex, int & tot) {
        int L = 1, R = 0, cnt = 0;tot = 0;
        sort(lset + 1, lset + size + 1);
        q[++R] = lset[1], q[++R] = lset[2];
        for(register int i = 3; i <= size; ++i) {
            while(L < R && AOnLeft(Itsec(q[R], q[R - 1]), lset[i].s, lset[i].t) <= 0) --R;
            while(L < R && AOnLeft(Itsec(q[L], q[L + 1]), lset[i].s, lset[i].t) <= 0) ++L;
            q[++R] = lset[i];
        }
        while(L < R && AOnLeft(Itsec(q[R], q[R - 1]), q[L].s, q[L].t) <= 0) --R;
        while(L < R && AOnLeft(Itsec(q[L], q[L + 1]), q[R].s, q[R].t) <= 0) ++L;
        if(R - L <= 1) return 0;
        for(register int i = L; i < R; ++i) 
            convex[++tot] = Itsec(q[i], q[i + 1]);
        convex[++tot] = Itsec(q[L], q[R]);
        convex[++tot] = convex[1];
        return 1;
    }
}

using namespace G2D;
Line lset[maxn];
P last, now, convex[maxn], bg;
int n, ec, size, cnt;

int main() {
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i) {
        scanf("%d", &ec);
        scanf("%lf %lf", &last.x, &last.y), bg = last;
        for(register int i = 2; i <= ec; ++i) {
            scanf("%lf %lf", &now.x, &now.y);
            lset[++size] = Line(last, now);
            last = now;
        }
        lset[++size] = Line(now, bg);
    }
    HPI(lset, size, convex, cnt);
    if(cnt < 3) return printf("0.000"), 0;
    printf("%.3lf\n", GetArea(convex, cnt) / 2.0);
    return 0;
}