hdu 4629 计算几何 扫描线 (2013多校联合)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const double eps = 1e-8;
#define pb push_back
inline int dcmp(double x) {
    if (fabs(x) < eps)
        return 0;
    return x > eps ? 1 : -1;
}
struct point {
    double x, y;
    point() {
    }
    point(const double &x, const double &y) :
            x(x), y(y) {
    }
    inline void in() {
        scanf("%lf%lf", &x, &y);
    }
    bool operator <(const point &t) const {
        return x + eps < t.x || (fabs(x - t.x) < eps && y + eps < t.y);
    }
    bool operator ==(const point &t) const {
        return !dcmp(x - t.x) && !dcmp(y - t.y);
    }
};
struct Line {
    point a, b;
    int tp;
    Line(const point &a, const point &b, const int &tp) :
            a(a), b(b), tp(tp) {
    }
    Line() {
    }
    bool operator <(const Line &t) const {
        return a < t.a || (a == t.a && b < t.b);
    }
};
double cross(const point &o, const point &a, const point &b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
bool segSegIntersect(const point &a, const point &b, const point &l, const point &r) { // 判两线段是否相交
    if (cross(a, b, l) * cross(a, b, r) < eps
            && cross(l, r, a) * cross(l, r, b) < eps)
        return 1; // 规范相交
    return 0;
}
//********两直线求交点， 先必须判是否相交(注意排除共线)
point intersect(const point &a, const point &b, const point &l, const point &r) {
    point ret = a;
    double t = ((a.x - l.x) * (l.y - r.y) - (a.y - l.y) * (l.x - r.x))
            / ((a.x - b.x) * (l.y - r.y) - (a.y - b.y) * (l.x - r.x));
    ret.x += (b.x - a.x) * t;
    ret.y += (b.y - a.y) * t;
    return ret;
}
int n;

Line line[22504], res[22504]; //line记录所有三角形的线段，   res记录夹在相邻两个x竖线之间的线段
double X[22504];			//记录所有端点和交点的X
int c1, c2, c3;				//   line的个数，     res的个数    X的个数

double ans[55];

int main() {
    int i, j, k, cas;
    scanf("%d", &cas);
    while (cas--) {
        c1 = c2 = c3 = 0;
        scanf("%d", &n);
        for (i = 0; i < n; i++) {
            point a, b, c, tp[5];
            for (j = 0; j < 3; j++) {
                tp[j].in();
                X[c3++] = tp[j].x;
            }
            if (!dcmp(cross(tp[0], tp[1], tp[2])))		//三点共线特判掉，不特判也没关系的
                continue;
            for (j = 0; j < 3; j++)					//两两枚举三角形的边
                for (k = j + 1; k < 3; k++) {
                    a = tp[j];
                    b = tp[k];
                    if (a.x == b.x)					//排除与x轴垂直的线段
                        continue;
                    if (b < a)
                        swap(a, b);
                    c = tp[3 - j - k];
                    line[c1++] = Line(a, b, dcmp(cross(a, b, c)));    //叉积判上下方非常方便
                }
        }
		//得到所有线段的交点
        for (i = 0; i < c1; i++)	
            for (j = i + 1; j < c1; j++) {
                if (!segSegIntersect(line[i].a, line[i].b, line[j].a,
                        line[j].b))
                    continue;
                point tp = intersect(line[i].a, line[i].b, line[j].a,
                        line[j].b);
                X[c3++] = tp.x;
            }
        sort(X, X + c3);		//X排序去重
		c3 = unique(X, X+c3)-X;
        for (i = 0; i <= n; i++)
            ans[i] = 0.0;
        for (i = 1; i < c3; i++) {    //枚举相邻的X  即  X[i-1] 与X[i]
            c2 = 0;
            for (j = 0; j < c1; j++)		//枚举所有三角形的边
                if (line[j].a.x <= X[i - 1] && X[i] <= line[j].b.x) {			//线段在该区域里面，确保有交点
                    point a = intersect(line[j].a, line[j].b, point(X[i-1], 0),
                            point(X[i-1], 1));
                    point b = intersect(line[j].a, line[j].b, point(X[i], 0),
                            point(X[i], 1));
                    res[c2++] = Line(a, b, line[j].tp);		//把夹在 X[i-1] 与X[i]这两条竖线之间的线段保存下来
                }
            sort(res, res + c2);			
            if (c2) {
                int deep = res[0].tp;
                for (j = 1; j < c2; j++) { //从下往上遍历所有线段并计算面积
                    double h = res[j].b.x - res[j].a.x;
                    double b = fabs(res[j - 1].a.y - res[j].a.y)
                            + fabs(res[j - 1].b.y - res[j].b.y);
                    if (deep)
                        ans[deep] += b * h / 2;	
                    deep += res[j].tp;		//修改度
                }
            }
        }

        for (i = 1; i <= n; i++)
            printf("%.10fn", ans[i]);
    }
    return 0;
}