#include #include #include #include using namespace std; const double EPS = 1e-9; double roundZero(long double d) { return abs(d) < EPS ? 0.0 : d; } #define rep(i, a, b) for(int i = a; i < (b); ++i) #define trav(a, x) for(auto& a : x) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair pii; typedef vector vi; template int sgn(T x) { return (x > 0) - (x < 0); } template struct Point { typedef Point P; T x, y; explicit Point(T x=0, T y=0) : x(x), y(y) {} bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); } bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } P operator+(P p) const { return P(x+p.x, y+p.y); } P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(T d) const { return P(x*d, y*d); } P operator/(T d) const { return P(x/d, y/d); } T dot(P p) const { return x*p.x + y*p.y; } T cross(P p) const { return x*p.y - y*p.x; } T cross(P a, P b) const { return (a-*this).cross(b-*this); } T dist2() const { return x*x + y*y; } double dist() const { return sqrt((double)dist2()); } // angle to x-axis in interval [-pi, pi] double angle() const { return atan2(y, x); } P unit() const { return *this/dist(); } // makes dist()=1 P perp() const { return P(-y, x); } // rotates +90 degrees P normal() const { return perp().unit(); } // returns point rotated 'a' radians ccw around the origin P rotate(double a) const { return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); } }; /* template pair lineInter(P s1, P e1, P s2, P e2) { auto d = roundZero((e1 - s1).cross(e2 - s2)); if (d == 0) // if parallel return {-(roundZero(s1.cross(e1, s2)) == 0), P(0, 0)}; auto p = s2.cross(e1, e2), q = s2.cross(e2, s1); return {1, (s1 * p + e1 * q) / d}; } */ template pair lineInter(P aa, P ab, P ba, P bb) { auto difv = ba-aa, av = ab-aa, bv = ba-bb; double d = roundZero(av.cross(bv)), fa = difv.cross(bv), fb = av.cross(difv); if (d == 0) // if parallel return {0, P(0, 0)}; if (d < 0) { d = -d; fa = -fa; fb = -fb; } auto t = aa + (av * fa) / d; return {1, t}; } typedef Point P; vector

polygonCut(const vector

& poly, P s, P e) { vector

res; rep(i,0,sz(poly)) { P cur = poly[i], prev = i ? poly[i-1] : poly.back(); bool side = roundZero(s.cross(e, cur)) < 0; if (side != (roundZero(s.cross(e, prev)) < 0)) { pair li = lineInter(s, e, cur, prev); if (li.first) res.push_back(li.second); } if (side) res.push_back(cur); } return res; } template T polygonArea2(vector>& v) { T a = v.back().cross(v[0]); rep(i,0,sz(v)-1) a += v[i].cross(v[i+1]); return a; } int main() { int n; scanf("%d", &n); int max = 0; vector

polygon; for(int i=0;i max) max = x; if (y > max) max = y; } vector

current; current.push_back(P(0, 0)); current.push_back(P(0, max)); current.push_back(P(max, max)); current.push_back(P(max, 0)); for (int i = 0; i < n; i++) { current = polygonCut(current, polygon[i], polygon[(i+1) % n]); } fprintf(stderr, "Poly size: %lu\n", current.size()); printf("%.9Lf\n", current.size() == 0 ? 0 : -polygonArea2(current) / 2.0); return 0; }