// implment 45min // debug1 25min // debug2 20min // debug3 50min #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; static const long double EPS = 1e-9; static const long double PI = acos(-1.0); #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define FOR(i, s, n) for (int i = (s); i < (int)(n); i++) #define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++) #define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++) #define MEMSET(v, h) memset((v), h, sizeof(v)) #include typedef complex Point; typedef vector Polygon; static const long double INF = 1e+10; #define CURR(P, i) (P[i]) #define NEXT(P, i) (P[(i + 1) % P.size()]) struct Line : public vector { Line() {;} Line(Point a, Point b) { push_back(a); push_back(b); } }; namespace std { bool operator<(const Point &lhs, const Point &rhs) { if (fabs(lhs.real() - rhs.real()) < EPS * 10 && fabs(lhs.imag() - rhs.imag()) < EPS * 10) { return false; } return lhs.real() == rhs.real() ? lhs.imag() < rhs.imag() : lhs.real() < rhs.real(); } } void PrintPolygon(const Polygon &p) { FORIT(it, p) { cout << *it << " "; } cout << endl; } inline long double cross(const Point &a, const Point &b) { return imag(conj(a) * b); } inline long double dot(const Point &a, const Point &b) { return real(conj(a) * b); } inline int ccw(Point a, Point b, Point c) { b -= a; c -= a; if (cross(b, c) > 0) { return 1; } if (cross(b, c) < 0) { return -1; } if (dot(b, c) < 0) { return 2; } if (norm(b) < norm(c)) { return -2; } return 0; } bool intersectLL(const Line &l, const Line &m) { return abs(cross(l[1] - l[0], m[1] - m[0])) > EPS || abs(cross(l[1] - l[0], m[0] - l[0])) < EPS; } bool intersectLS(const Line &l, const Line &s) { return cross(l[1] - l[0], s[0] - l[0]) * cross(l[1] - l[0], s[1] - l[0]) < EPS; } bool intersectLP(const Line &l, const Point &p) { return abs(cross(l[1] - p, l[0] - p)) < EPS; } bool intersectSS(const Line &s, const Line &t) { return ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 && ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0; } bool intersectSP(const Line &s, const Point &p) { return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS; } Point crosspointSS(const Line &l, const Line &m) { long double A = cross(l[1] - l[0], m[1] - m[0]); long double B = cross(l[1] - l[0], l[1] - m[0]); if (abs(A) < EPS && abs(B) < EPS) { //assert(false); if (intersectSP(l, m[0])) { return m[0]; } if (intersectSP(l, m[1])) { return m[1]; } if (intersectSP(m, l[0])) { return l[0]; } if (intersectSP(m, l[1])) { return l[1]; } return m[0]; } if (abs(A) < EPS) { assert(false); } return m[0] + B / A * (m[1] - m[0]); } long double Area(const Polygon &p) { long double ret = 0; for (int i = 0; i < (int)p.size(); i++) { ret += cross(CURR(p, i), NEXT(p, i)); } //cout << ret / 2.0 << endl; assert(ret > -EPS); return ret / 2.0; } //============================================================ typedef set Edges; typedef vector Graph; int n, m; Point ps[10010]; map vertexs; vector revVertexs; Graph g; vector > args; void PrintArgs(int i) { FORIT(it, args[i]) { cout << it->first << " " << it->second << endl; } cout << endl; } int main() { while (scanf("%d", &n) > 0) { // Init & Input m = 0; vertexs.clear(); revVertexs.clear(); g.clear(); args.clear(); REP(i, n) { long double x, y; scanf("%Lf %Lf", &x, &y); ps[i] = Point(x, y); } // Arrangement REP(i, n) { if (vertexs.count(ps[i])) { continue; } vertexs[ps[i]] = m++; revVertexs.push_back(ps[i]); } REP(j, n - 1) { REP(i, j) { Line s1 = Line(ps[i], ps[i + 1]); Line s2 = Line(ps[j], ps[j + 1]); if (intersectSS(s1, s2)) { Point p = crosspointSS(s1, s2); if (vertexs.count(p)) { continue; } vertexs[p] = m++; revVertexs.push_back(p); } } } Graph g(m); REP(i, n - 1) { Line s = Line(ps[i], ps[i + 1]); vector > onLine; FORIT(it, vertexs) { if (intersectSP(s, it->first)) { onLine.push_back(make_pair(abs(it->first - ps[i]), it->second)); } } sort(onLine.begin(), onLine.end()); REP(i, onLine.size() - 1) { int from = onLine[i].second; int to = onLine[i + 1].second; g[from].insert(to); g[to].insert(from); } } // Add Banpei int last = vertexs.rbegin()->second; vertexs[Point(1e+100, 0)] = m; revVertexs.push_back(Point(1e+100, 0)); g[last].insert(m); g.push_back(set()); g[m].insert(last); m++; // Create Args args.resize(m); REP(from, m) { Point p1 = revVertexs[from]; FORIT(it, g[from]) { int to = *it; Point p2 = revVertexs[to]; long double theta = -arg(p2 - p1); // clockwise args[from][theta] = to; args[from][theta + 2.0 * PI] = to; } args[from][1e+100] = 0xdeadbeaf; } // Calc Area long double ans = 0.0; vector > used(m); REP(start, m) { FORIT(it, args[start]) { if (it->first == 1e+100 || used[start][it->first]) { continue; } //cout << "Begin:" << start << endl; bool outer = false;; Polygon poly; poly.push_back(revVertexs[start]); int from = start; long double theta = it->first - 2 * EPS; while (true) { //cout << theta << endl; assert(args[from].size() > 1); map::iterator it = args[from].upper_bound(theta + EPS); theta = it->first; long double ntheta = it->first + PI; long double to = it->second; while (ntheta >= PI) { ntheta -= 2 * PI; } poly.push_back(revVertexs[to]); if (to == m - 1) { outer = true; } if (used[from][theta]) { break; } //cout << from << " " << to << " " << theta << endl; //PrintArgs(from); //cout << args[from].size() << endl; // Erase Use Edge used[from][theta] = true; { long double t1 = args[from].lower_bound(theta - 2 * PI - EPS)->first; long double t2 = args[from].lower_bound(theta + 2 * PI - EPS)->first; if (fabs(t1 - (theta - 2 * PI)) < EPS * 10) { used[from][t1] = true; } if (fabs(t2 - (theta + 2 * PI)) < EPS * 10) { used[from][t2] = true; } } from = to; theta = ntheta; } //PrintPolygon(poly); if (!outer) { ans += Area(poly); } //cout << "End" << endl; //cout << endl; } } printf("%.10Lf\n", ans); } }