Rockdu's Blog

Description

Input

Output

Sample Input

Sample Output

HINT

Source

之前做了一些像扫描线的题，今天终于A了扫描线始祖。

这道题的思想很简单：先把所有边的顶点和交点求出来，对这些点按横坐标排序，沿着每一个点做一根垂直X轴的线。这样做有什么好处呢？我们发现任意相邻的两根线中间只可能截出若干个不相交（仅有包含关系）的三角形和梯形，这样我们只要对于每两根相邻的线求出：中间截出的梯形和三角形的面积之和即可。那么怎么计算这个面积呢？

如果老老实实截取两条直线，会面临很多麻烦的情况，各种特判也不在例外。但是我们可以换一种思路——发现两条平行线间，高是一定的。我们可以截取这些三角形和梯形的中位线（中位线乘高计算面积很方便）！这样我们只用进行一次截取，并且计算答案很简单——所有线段排序后取并集，总长乘上高就是答案！不仅精简了代码，还缩小了常数。

 代码如下：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
 
namespace G2D {
    #define T long double
    #define eps (1e-15)
    inline int sg(T a) {return (a > -eps) - (a < eps);}
    struct P {T x, y;P(const T &_x, const T &_y):x(_x), y(_y){}P(){}};
    struct Line {P s, t;int id;Line(const P &_s, const P &_t):s(_s), t(_t){}Line(){}};
    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 T &A, const P &B) {return P(A * B.x, A * B.y);}
    inline T operator *(const P &A, const P &B) {return A.x * B.y - B.x * A.y;}
    inline bool cmp_x(const P &A, const P &B) {return A.x < B.x;}
    inline bool cmp_y(const P &A, const P &B) {return A.y < B.y;}
    inline int AOnLeft(const P &A, const P &B) {return sg(B * A);}
    inline int AOnLeft(const P &A, const Line &B) {return sg((B.t - A) * (B.s - A));}
    inline bool Crsed(const Line &A, const Line &B) {
        return (AOnLeft(A.s, B) + AOnLeft(A.t, B) == 0) && ((AOnLeft(B.s, A) + AOnLeft(B.t, A) == 0));
    }
    inline P Itsec(const Line &A, const Line &B) {
        T s1 = abs((B.s - A.s) * (B.t - A.s)), s2 = abs((B.s - A.t) * (B.t - A.t));
        return (s1 / (s1 + s2)) * (A.t - A.s) + A.s;
    }
}
 
using namespace G2D;
const int maxn = 9e4 + 5;
Line segs[maxn];P ints[maxn];
int lcnt, pcnt, n, cnt, is_In, ptcnt, lscnt, vis[maxn];
long double layer[maxn], pt[maxn], now, h, ans;
double rx, ry;
struct pdd{
    long double x, y;
    pdd(const long double &_x, const long double &_y):x(_x), y(_y){if(x > y)swap(x, y);}pdd(){}
    bool operator <(const pdd &A) const{return !sg(x - A.x) ? y > A.y : x < A.x;}
}ls[maxn];
int main() {
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i) {
        for(register int j = 1; j <= 3; ++j)
            scanf("%lf %lf", &rx, &ry), ints[++pcnt] = P(rx, ry);
        segs[++lcnt] = Line(ints[pcnt - 2], ints[pcnt - 1]), segs[lcnt].id = i;
        segs[++lcnt] = Line(ints[pcnt - 1], ints[pcnt]), segs[lcnt].id = i;
        segs[++lcnt] = Line(ints[pcnt], ints[pcnt - 2]), segs[lcnt].id = i;
    }
    for(register int i = 1; i <= lcnt; ++i)
        for(register int j = i + 1; j <= lcnt; ++j)
            if(Crsed(segs[i], segs[j]) && sg((segs[i].t - segs[i].s) * (segs[j].t - segs[j].s)))
                ints[++pcnt] = Itsec(segs[i], segs[j]);
    sort(ints + 1, ints + pcnt + 1, cmp_x);
    layer[++cnt] = ints[1].x;
    for(register int i = 2; i <= pcnt; ++i)
        if(ints[i].x != ints[i - 1].x) layer[++cnt] = ints[i].x;
    for(register int i = 1; i < cnt; ++i) {
        now = (layer[i + 1] + layer[i]) / 2.0;
        h = layer[i + 1] - layer[i], lscnt = ptcnt = 0;
        memset(vis, 0, sizeof(vis));
        for(register int j = 1; j <= lcnt; ++j)
            if((segs[j].s.x > now) ^ (segs[j].t.x > now))
                if(!vis[segs[j].id]) pt[segs[j].id] = Itsec(segs[j], Line(P(now, 0), P(now, 100))).y, vis[segs[j].id] = 1;
                else ls[++lscnt] = pdd(pt[segs[j].id], Itsec(segs[j], Line(P(now, 0), P(now, 100))).y);
        sort(ls + 1, ls + lscnt + 1);
        long double L = -1e100, R = -1e100;
        for(register int j = 1; j <= lscnt; ++j) {
            if(R >= ls[j].x && R <= ls[j].y) R = ls[j].y;
            else if(ls[j].x > R) 
            ans += h * (R - L), L = ls[j].x, R = ls[j].y;
        }
        ans += h * (R - L);
    }
    printf("%.2lf", (double)ans);
    return 0;
}