/*
fig -> figura initiala
Se creeaza bounding-box-ul figurii. Acesta este poligonul solutie curent.
Se iau toate muchiile figurii initiale si se intersecteaza cu poligonul
solutie curent (intre punctele poligonului solutie se monteaza punctul de intersectie
al poligonului solutie cu muchia curenta din fig)
Dupa aceea, se elimina din poligonul solutie toate punctele care nu sunt "vazute"
de muchia curenta din fig (se afla in exterior).
*/
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const double INF = 2000000000.0;
const double ERROR = 0.000001;
inline double max(double a, double b)
{
return (a>b)?a:b;
}
inline double min(double a, double b)
{
return (a<b)?a:b;
}
inline double modul(double x)
{
return (x >= 0)?x:-x;
}
struct punct_i
{
int x,y;
};
struct punct
{
double x,y;
bool operator == (punct);
};
bool punct::operator == (punct p)
{
return ((modul(x - p.x) <= ERROR)&&(modul(y - p.y) <= ERROR));
}
struct segment
{
punct a,b;
segment();
segment(punct,punct);
};
segment::segment()
{
}
segment::segment(punct pa, punct pb)
{
a = pa;
b = pb;
}
struct dreapta
{
double a,b,c;
dreapta();
dreapta(segment);
};
dreapta::dreapta()
{
}
dreapta::dreapta(segment s)
{
a = s.a.y - s.b.y;
b = s.b.x - s.a.x;
c = s.a.x * s.b.y - s.b.x * s.a.y;
}
inline double semn_punct_dreapta(punct p, dreapta d)
{
if (modul(d.a * p.x + d.b * p.y + d.c) <= ERROR)//det == 0
return 0;
return (d.a * p.x + d.b * p.y + d.c)>0?1:-1;
}
bool exista_intersectie_segmente(segment o, segment p)
{
if (semn_punct_dreapta(p.a, dreapta(o)) == semn_punct_dreapta(p.b, dreapta(o))) //acelasi semn nu e bine
return false;
if (semn_punct_dreapta(o.a, dreapta(p)) == semn_punct_dreapta(o.b, dreapta(p))) //acelasi semn nu e bine
return false;
return true;
}
inline bool exista_intersectie_segment_dreapta(segment s, dreapta d)
{
return semn_punct_dreapta(s.a, d) != semn_punct_dreapta(s.b, d); //acelasi semn nu e bine
}
inline bool exista_intersectie_drepte(dreapta d1, dreapta d2)
{
return modul(d1.a*d2.b - d2.a * d1.b) > ERROR;//det > 0
}
punct intersectie_drepte(dreapta d1, dreapta d2)
{
punct p;
double det = d1.a*d2.b - d2.a * d1.b; //det = a1*b2 - a2*b1;
if (modul(det) <= ERROR)//det == 0
{
p.x = INF;
p.y = INF;
return p;
}
p.x = (d1.b*d2.c - d2.b * d1.c)/det; //p.x = (b1*c2 - b2*c1)/det;
p.y = (d2.a*d1.c - d1.a*d2.c)/det; //p.y = (a2*c1 - a1*c2)/det;
return p;
}
double arie_poligon_cu_semn(vector<punct> fig)
{
double arie_fig = 0;
double x1,y1,x2,y2;
for (unsigned int i = 1; i < fig.size()-1; ++i)
{
x1 = fig[i].x - fig[0].x;
y1 = fig[i].y - fig[0].y;
x2 = fig[i+1].x - fig[0].x;
y2 = fig[i+1].y - fig[0].y;
arie_fig += x1 * y2 - x2 * y1;
}
arie_fig /= 2;
return arie_fig;
}
inline double arie_poligon(vector<punct> fig)
{
return modul(arie_poligon_cu_semn(fig));
}
vector<punct> bounding_box(vector<punct> fig, double orientare)
{
double xmax=0,xmin=INF,ymax=0,ymin=INF;
vector<punct> v;
punct p;
for (unsigned int i = 0; i < fig.size(); ++i)
{
xmin = min(xmin,fig[i].x);
xmax = max(xmax,fig[i].x);
ymin = min(ymin,fig[i].y);
ymax = max(ymax,fig[i].y);
}
if (orientare > 0)//trigonometric
{
p.x = xmin, p.y = ymax; v.push_back(p);
p.x = xmin, p.y = ymin; v.push_back(p);
p.x = xmax, p.y = ymin; v.push_back(p);
p.x = xmax, p.y = ymax; v.push_back(p);
}
else
{
p.x = xmin, p.y = ymax; v.push_back(p);
p.x = xmax, p.y = ymax; v.push_back(p);
p.x = xmax, p.y = ymin; v.push_back(p);
p.x = xmin, p.y = ymin; v.push_back(p);
}
return v;
}
void adaugare_intersectie_dreapta_poligon(dreapta d, vector<punct> &fig)
{
segment s;
for (unsigned int i = 0; i < fig.size()-1; ++i)
{
s.a = fig[i];
s.b = fig[i+1];
if (!exista_intersectie_segment_dreapta(s,d))
continue;
fig.insert(fig.begin()+i+1,intersectie_drepte(dreapta(s),d));
++i;
}
s.a = fig[fig.size()-1];
s.b = fig[0];
if (exista_intersectie_segment_dreapta(s,d))
fig.insert(fig.begin()+fig.size(),intersectie_drepte(dreapta(s),d));
vector<punct>::iterator poz = unique(fig.begin(),fig.end());
fig.resize(poz - fig.begin());
}
void eliminare_puncte_sub_dreapta_poligon(dreapta d, vector<punct> &fig, double orientare)
{
for (unsigned int i = 0; i < fig.size(); ++i)
{
if ((orientare > 0)&&(semn_punct_dreapta(fig[i],d) >= 0))
continue;
if ((orientare < 0)&&(semn_punct_dreapta(fig[i],d) <= 0))
continue;
fig.erase(fig.begin()+i);
--i;//element sters.
}
}
vector<punct> fig; int n;
vector<punct> sol;
void citire()
{
punct_i pi;
punct p;
scanf("%i",&n);
for (int i = 0; i < n; ++i)
{
scanf("%i%i",&pi.x,&pi.y);
p.x = (double)pi.x;
p.y = (double)pi.y;
fig.push_back(p);
}
}
void parcurgere_muchii()
{
dreapta d;
double arie_sol = arie_poligon_cu_semn(sol);
for (int i = 0; i < n; ++i)
{
d = dreapta(segment(fig[i],fig[i+1]));
adaugare_intersectie_dreapta_poligon(d,sol);
eliminare_puncte_sub_dreapta_poligon(d,sol,arie_sol);
}
d = dreapta(segment(fig[n-1],fig[0]));
adaugare_intersectie_dreapta_poligon(d,sol);
eliminare_puncte_sub_dreapta_poligon(d,sol,arie_sol);
}
int main()
{
freopen("camera.in","r",stdin);
freopen("camera.out","w",stdout);
citire();
sol = bounding_box(fig,arie_poligon_cu_semn(fig));
parcurgere_muchii();
if (sol.size() < 3)
printf("0.00");
else
printf("%.2lf",arie_poligon(sol));
return 0;
}