gallery.cpp

#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define long long long
#define f1(i,n) for (int i=1; i<=n; i++)
#define f0(i,n) for (int i=0; i<n; i++)
typedef pair<double, double> lflf;
typedef pair<lflf, double> line;
#define X first
#define Y second

struct vertex : lflf {
    vertex *Next, *Prev;
    int Visited; bool Removed;
    void clear(){ Next=Prev=NULL; Visited=0; Removed=false; }
    vertex(lflf a){ clear(); X=a.X, Y=a.Y; }
    vertex(double x, double y){ clear(); X=x, Y=y; }
    vertex(){ clear(); }
};

int cnt=0, Jumps=0;
void NIE(){ cout << "0.00" << endl; exit(0); }
#define f2(I, A) for (vertex *I=(cnt++, A); changable(I->Visited, cnt); I=I->Next)
ostream& operator << (ostream& cout, line d)
    { return cout << d.X.X << "x+" << d.X.Y << "y=" << d.Y; }
bool changable(int &a, int b)
    { if (a==b) return false; return a=b, true; }
double abs(double a, double b)
    { return a>b?a-b:b-a; }
lflf operator - (lflf a, lflf b)
    { return lflf(a.X-b.X, a.Y-b.Y); }
lflf fn(lflf a)
    { return lflf(-a.Y, a.X); }
line xxfd(lflf a, lflf b)
    { lflf n = fn(a-b); return line(n, n.X*a.X+n.Y*a.Y); }
bool ddfx(line a, line b, lflf &I){
    double D = a.X.X*b.X.Y-a.X.Y*b.X.X;
    if (abs(D, 0)<=1e-9) return false;
    double DX = a.Y*b.X.Y-a.X.Y*b.Y;
    double DY = a.X.X*b.Y-a.Y*b.X.X;
    I=lflf(DX/D, DY/D);
    return true;
}
double xdf(lflf a, line d)
    { return d.X.X*a.X+d.X.Y*a.Y-d.Y; }
int sign(double a)
    { if (abs(a, 0)<=1e-9) return 0; return a>0?1:-1; }
int sign(lflf a, line d)
    { return sign(xdf(a, d)); }


void show(vertex* A){
    printf("Show()\n");
    f2(I,A) printf("%X, %X, %X, %lf, %lf\n", I->Prev, I, I->Next, I->X, I->Y);
}
ostream& operator << (ostream& cout, vertex* a)
    { return cout << a->X << "," << a->Y; }
void insert(vertex* b, vertex* a){
    b->Next=a->Next; a->Next->Prev=b;
    a->Next=b; b->Prev=a;
//  cout << "Insert " << b << endl;
}
void remove(vertex* a){
    a->Prev->Next=a->Next;
    a->Next->Prev=a->Prev;
//  cout << "Remove " << a << endl;
    delete a;
}
stack<vertex*> RemoveLater;
void remove_later(vertex* a){
    RemoveLater.push(a);
    a->Removed=true;
}
void remove_now(){
    while (RemoveLater.size()) {
        remove(RemoveLater.top());
        RemoveLater.pop();
    }
}

#define N 12309
int n;
vertex* a[N];

vertex* crop(line d, vertex* A){
//  cout << "Crop " << d << ";" << A << endl;
    f2(I,A) if (sign(*I, d)!=0 && sign(*I, d) + sign(*I->Next, d) == 0) {
//      cout << "sign " << I << ";" << d << "=" << sign(*I, d) << endl;
//      cout << "sign " << I->Next << ";" << d << "=" << sign(*I->Next, d) << endl;
//      cin.ignore(1);
        lflf K;
        if (ddfx(d, xxfd(*I, *I->Next), K))
        insert(new vertex(K), I);
    }
    f2(I,A) if (sign(*I, d)<0) remove_later(I);
    while (A->Removed) { if (++Jumps>10000000) NIE(); A=A->Next; }
    remove_now();
    return A;
}
double area(lflf a, lflf b){
    return (a.X-b.X)*(a.Y+b.Y);
}
double area(vertex* A){
    double Sum=0;
    f2(I,A) Sum += area(*I, *I->Next);
    return abs(Sum/2, 0);
}

main(){
    scanf("%d", &n);
    f1(i,n) { int x, y; scanf("%d%d", &x, &y); a[i]=new vertex(1.*x, 1.*y); }
    for (int j=n, i=1; i<=n; j=i++) { a[j]->Next=a[i]; a[i]->Prev=a[j]; }
    vertex *Root = a[1];
//  show(Root);

    vector<line> T;
    f2(I,Root) T.push_back(xxfd(*I, *I->Next));
    f0(i,T.size()) Root=crop(T[i], Root);
    cout.precision(2);
    cout << fixed << area(Root) << endl;
//  show(Root);
}