wy's Blog

2618: [Cqoi2006]凸多边形

Description

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

 

则相交部分的面积为5.233。

Input

Output

Sample Input

Sample Output

HINT

半平面交模板题， 不解释~

#include <cmath> 
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int MaxN = 510;
const double eps = 1e-7;
int T, n, m, que[MaxN], ql, qr;
double ans;
struct point {
    double x, y;
    point (const double &a = 0, const double &b = 0) {
        x = a, y = b;
    }
    double operator * (const point &b) const {
        return x * b.y - b.x * y;
    }
    point operator * (const double &b) const {
        return point(x * b, y * b);
    }
    point operator / (const double &b) const {
        return point(x / b, y / b);
    }
    point operator + (const point &b) const {
        return point(x + b.x, y + b.y);
    }
    point operator - (const point &b) const {
        return point(x - b.x, y - b.y);
    }
}P[MaxN]; 
struct line {
    point a, b;
    int k;
    line() { } 
    line (const point &x, const point &y) {
        a = x, b = y;
    }
}L[MaxN];
int sgn(const double &x) {
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}
bool cmp(const line &a, const line &b) {
    if (a.k != b.k) return a.k < b.k;
    return sgn((a.b - a.a) * (b.b - b.a)) > 0;
}
point JD(const line &a, const line &b) {
    double s1 = (b.b - b.a) * (a.a - b.a), s2 = (b.b - b.a) * (a.b - b.a);
    point dir = a.b - a.a;
    return a.a + dir * s1 / (s1 - s2);
}
int main()
{
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &m);
        for (int i = 0; i < m; ++i) 
            scanf("%lf%lf", &P[i].x, &P[i].y);
        for (int i = 0; i < m; ++i)
            L[++n] = line(P[i], P[(i + 1) % m]);
    }
    for (int i = 1; i <= n; ++i)
        L[i].k = sgn(L[i].b.y - L[i].a.y) ? sgn(L[i].b.y - L[i].a.y) : sgn(L[i].b.x - L[i].a.x);
    sort(L + 1, L + n + 1, cmp);
    ql = 1, qr = 0;
    for (int i = 1; i <= n; ++i) {
        while (ql < qr && sgn((L[i].b - L[i].a) * (P[qr - 1] - L[i].a)) < 0) --qr;
        while (ql < qr && sgn((L[i].b - L[i].a) * (P[ql] - L[i].a)) < 0) ++ql;
        que[++qr] = i;
        if (ql < qr && sgn((L[i].b - L[i].a) * (L[que[qr - 1]].b - L[que[qr - 1]].a)) == 0) {
            //if (sgn((L[que[qr]].b - L[que[qr]].a) * (L[que[qr - 1]].a - L[que[qr]].a)) <= 0) que[qr - 1] = que[qr];  这句是错的！！！ 
			if (sgn((L[que[qr - 1]].b - L[que[qr - 1]].a) * (L[que[qr]].b - L[que[qr - 1]].a)) >= 0) que[qr - 1] = que[qr];
            --qr;
        }
        if (ql < qr) P[qr - 1] = JD(L[que[qr - 1]], L[que[qr]]);
    }
    while (ql + 1 < qr && sgn((L[que[ql]].b - L[que[ql]].a) * (P[qr - 1] - L[que[ql]].a)) < 0) --qr;
    while (ql + 1 < qr && sgn((L[que[qr]].b - L[que[qr]].a) * (P[ql] - L[que[qr]].a)) < 0) ++ql;
    P[qr] = JD(L[que[ql]], L[que[qr]]);
    for (int i = ql; i < qr; ++i)
        ans += P[i] * P[i + 1];
    ans += P[qr] * P[ql];
    printf("%.3lf\n", fabs(ans) / 2);
} 

后记——

2016.3.5

wy在写 [Wf2015] Asteroids 时发现了板子的错误，

在两条直线平行时去掉其中一条出了点偏差

   if (ql < qr && sgn((L[i].b - L[i].a) * (L[que[qr - 1]].b - L[que[qr - 1]].a)) == 0) {
            //if (sgn((L[que[qr]].b - L[que[qr]].a) * (L[que[qr - 1]].a - L[que[qr]].a)) <= 0) que[qr - 1] = que[qr];  这句是错的！！！ 
			if (sgn((L[que[qr - 1]].b - L[que[qr - 1]].a) * (L[que[qr]].b - L[que[qr - 1]].a)) >= 0) que[qr - 1] = que[qr];
            --qr;
        }
    }

wy认为上下两句是差不多的呀，可它就是错了呀，不懂的啊QAQ