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
| #include <bits/stdc++.h> using namespace std;
const double eps = 1e-8; inline int sgn(double x) { if (fabs(x) < eps) return 0; return (x < 0) ? -1 : 1; } struct point{ double x, y; point(double xx = 0.0, double yy = 0.0): x(xx), y(yy) {} }; typedef point vec;
struct edge{ point a, b; edge(point aa = point(), point bb = point()): a(aa), b(bb) {} };
inline vec operator + (vec A, vec B) { return vec(A.x + B.x, A.y + B.y); } inline vec operator - (point A, point B) { return vec(A.x - B.x, A.y - B.y); } inline vec operator * (vec A, double p) { return vec(A.x * p, A.y * p); } inline vec operator / (vec A, double p) { return vec(A.x / p, A.y / p); } inline bool operator < (const point A, const point B) { return A.x < B.x || (sgn(A.x - B.x) == 0 && A.y < B.y); } inline double dot(vec A, vec B) { return A.x * B.x + A.y * B.y; } inline double cross(vec A, vec B) { return A.x * B.y - A.y * B.x; } inline point line_intersection(point P, point P2, point Q, point Q2) { vec v = P - P2, w = Q - Q2; vec u = P - Q; double t = cross(w, u) / cross(v, w); return P + v * t; } inline bool GFXJ(point A, point B, point P, point Q) { double c1 = cross(B - A, P - A), c2 = cross(B - A, Q - A); double c3 = cross(Q - P, A - P), c4 = cross(Q - P, B - P); if (sgn(cross(B - A, P - A)) == 0) return 0; return sgn(c1) * sgn(c2) < 0 && sgn(c3) * sgn(c4) < 0; } inline bool BGFXJ(point A, point B, point P, point Q) { double c1 = cross(B - A, P - A), c2 = cross(B - A, Q - A); double c3 = cross(Q - P, A - P), c4 = cross(Q - P, B - P); if (sgn(cross(B - A, P - A)) == 0) return 0; return sgn(c1) * sgn(c2) <= 0 && sgn(c3) * sgn(c4) <= 0; }
int n, tot, ee; double ans; point p[100005]; edge e[305]; vector<pair<double, double> > sol;
double solve(double x) { sol.clear(); point pp = point(x, -2e6); point q = point(x, 2e6); for (int i = 1; i <= ee; i += 3) { if (BGFXJ(pp, q, e[i].a, e[i].b) + BGFXJ(pp, q, e[i+1].a, e[i+1].b) + BGFXJ(pp, q, e[i+2].a, e[i+2].b) < 2) { continue; } pair<double, double> tmp; tmp.first = 2e6, tmp.second = -2e6; for (int j = 0; j <= 2; j++) { if (BGFXJ(pp, q, e[i+j].a, e[i+j].b)) { double now = line_intersection(pp, q, e[i+j].a, e[i+j].b).y; tmp.first = min(tmp.first, now); tmp.second = max(tmp.second, now); } } sol.push_back(tmp); } sort(sol.begin(), sol.end()); if (!sol.size()) return 0; double lst = sol[0].first, ret = 0; for (int i = 0; i < sol.size(); i++) { if (sol[i].second <= lst) continue; if (sol[i].first > lst) ret += sol[i].second - sol[i].first; else ret += sol[i].second - lst; lst = sol[i].second; } return ret; }
int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%lf %lf %lf %lf %lf %lf", &p[tot+1].x, &p[tot+1].y, &p[tot+2].x, &p[tot+2].y, &p[tot+3].x, &p[tot+3].y); if (p[tot+1].x == p[tot+2].x) p[tot+2].x += 0.001; else if (p[tot+1].x == p[tot+3].x) p[tot+3].x += 0.001; else if (p[tot+2].x == p[tot+3].x) p[tot+3].x += 0.001; e[++ee] = edge(p[tot+1], p[tot+2]); e[++ee] = edge(p[tot+2], p[tot+3]); e[++ee] = edge(p[tot+3], p[tot+1]); tot += 3; } for (int i = 1; i <= ee; i++) { for (int j = i + 1; j <= ee; j++) { if (GFXJ(e[i].a, e[i].b, e[j].a, e[j].b)) { p[++tot] = line_intersection(e[i].a, e[i].b, e[j].a, e[j].b); } } } sort(p + 1, p + tot + 1); double lst = 0, lstx = 114514, now = 0; for (int i = 1; i <= tot; i++) { now = solve(p[i].x); if (sgn(lstx - 114514) != 0) { ans += (p[i].x - lstx) * (now + lst) / 2; } lstx = p[i].x; lst = now; while (p[i+1].x == p[i].x) i++; } printf("%.2lf\n", ans); return 0; }
|