#include #include #include #include #include using namespace std; #define double long double struct point { double x, y; point(double x=0, double y=0): x(x), y(y) {} point operator*(double c) const { return point(c*x, c*y); } point operator+(const point &p) const { return point(x+p.x, y+p.y); } point operator-(const point &p) const { return point(x-p.x, y-p.y); } point operator-() const { return point(-x, -y); } double dot(const point &p) const { return x*p.x + y*p.y; } double cross(const point &p) const { return x*p.y - y*p.x; } int quadrant() const { if (y > 0 && x >= 0) return 0; if (x < 0 && y >= 0) return 1; if (y < 0 && x <= 0) return 2; return 3; } bool operator<(const point &p) const { int q1 = quadrant(), q2 = p.quadrant(); if (q1 != q2) return q1 < q2; return cross(p) > 0; } }; struct ray { point P, dP; ray(point P=point(), point dP=point()): P(P), dP(dP) {} point isect(ray &L) const { double det = dP.cross(L.dP); double s = fabs(det) > 1e-9 ? L.dP.cross(P-L.P)/det : -1e30; return P + dP*s; } bool operator<(const ray &L) const { return dP < L.dP; } }; double area(const vector &P) { double res = 0.0; for (int i = 0, j = P.size()-1; i < P.size(); j = i++) res += P[j].P.cross(P[i].P); return res/2.0; } int main(int argc, char **argv) { int n; scanf("%d", &n); vector segs(n); for (int i = 0; i < n; ++i) scanf("%Lf%Lf", &segs[i].P.x, &segs[i].P.y); for (int i = 0; i < n; ++i) segs[i].dP = (segs[(i+n-1)%n].P - segs[i].P); sort(segs.begin(), segs.end()); int d = 0; for (int i = 1; i < n; ++i) { if (segs[d] < segs[i]) segs[++d] = segs[i]; else if (segs[i].dP.cross(segs[i].P - segs[d].P) > 0) segs[d] = segs[i]; } segs.resize(d+1); segs.push_back(segs.front()); n = segs.size(); vector P(1, segs[0]); auto add_line = [&](const ray &L) { auto q = L.isect(P.back()); while (P.size() > 1 && P.back().dP.dot(q-P.back().P) <= 0) { P.pop_back(); q = L.isect(P.back()); } P.push_back(ray(q, L.dP)); }; for (int i = 1; i < n; ++i) add_line(segs[i]); int a = 0; while (a+1 < P.size()-1 && P[a].dP.dot(P.back().P-P[a+1].P) > 0) { ++a; P.pop_back(); add_line(P[a]); } P = vector(P.begin() + a + 1, P.end()); printf("%.9Lf\n", area(P)); if (argc > 1) { printf("%d\n", P.size()); for (auto &p: P) printf("%lf %lf\n", p.P.x, p.P.y); } }