Cod sursa(job #2338068)

Utilizator patcasrarespatcas rares danut patcasrares Data 6 februarie 2019 22:36:00
Problema Camera Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.35 kb
#include<fstream>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector>
#include<iomanip>
#include<set>
#include<algorithm>
#define pb push_back
#define x first
#define y second
using namespace std;
ifstream fin("camera.in");
ofstream fout("camera.out");
const int DN=2e6+5;
const double eps=1e-7;
int n,nrs;
typedef pair<double,double>pdd;
pdd a[DN];
double r,val;
pair<int,pdd> s[DN];
double det(pdd A,pdd B,pdd C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}
int cmp(pdd A,pdd B)
{
	return atan2(A.y,A.x)<atan2(B.y,B.x);
}
void calc(pair<pdd,pdd> A,double &a,double &b,double &c)
{
	a=A.x.y-A.y.y;
	b=A.y.x-A.x.x;
	c=A.x.x*A.y.y-A.y.x*A.x.y;
}
pdd pct(pdd A,pdd B,double aa,double ab,double ac)
{
	if(A.x<B.x)
	{
		if(abs(ab)<eps)
			return {1e6,B.y};
		return {1e6,(-ac-aa*1e6)/ab};
	}
	if(A.x>B.x)
	{
		if(abs(ab)<eps)
			return {-1e6,B.y};
		return {-1e6,(-ac+aa*1e6)/ab};
	}

	if(A.y<B.y)
	{
		if(abs(aa)<eps)
			return {B.x,1e6};
		return {(-ac-ab*1e6)/aa,1e6};
	}
	if(A.y>B.y)
	{
		if(abs(aa)<eps)
			return {B.x,-1e6};
		return {(-ac+ab*1e6)/aa,-1e6};
	}
}
void ins2(pdd A)
{
	nrs++;
	s[nrs]={1,A};
}
int nr;
pdd b[DN];
int insidet(pdd A,pdd B,pdd C,pdd D)
{
	double rez;
	rez=abs(det(A,B,C));
	rez-=abs(det(A,B,D));
	rez-=abs(det(A,C,D));
	rez-=abs(det(C,B,D));
	return abs(rez)<eps;
}
int inside(pair<pdd,pdd> A,double rx,double ry)
{
	return 1;
}
void sol(pair<pdd,pdd> A,pair<pdd,pdd> B)
{
	double aa=0,ab=0,ac=0,ba=0,bb=0,bc=0,rx=0,ry=0,rz=0,t=0;
	calc(A,aa,ab,ac);
	calc(B,ba,bb,bc);
	if(abs(aa)<=eps)
	{
		ry=(-ac)/ab;
		if(abs(ba)<=eps)
		{
			return;
		}
		rx=-bc-ry*bb;
		rx/=ba;
		if(inside(A,rx,ry)&&inside(B,rx,ry))
            ins2({rx,ry});
		return;
	}
	t=ba/aa;
	ab*=t;
	ac*=t;
	ab-=bb;
	ac-=bc;
	if(abs(ab)<=eps)
	{
		return;
	}
	ry=(-ac)/ab;
	calc(A,aa,ab,ac);
	rx=-ac-ry*ab;
	rx/=aa;
	if(inside(A,rx,ry)&&inside(B,rx,ry))
		ins2({rx,ry});
}
void ins(pdd A,pdd B,pdd C)
{
	for(int i=1;i<=nrs;i++)
		if(s[i].x==1)
		if(!insidet(A,B,C,s[i].y))
			s[i].x=0;
}
void add(int poz)
{
	pdd A=a[poz],B,C;
	double aa,ab,ac;
	pair<pdd,pdd>zz;
	calc({a[poz],a[poz-1]},aa,ab,ac);
	B=pct(A,a[poz-1],aa,ab,ac);
	calc({a[poz],a[poz+1]},aa,ab,ac);
	C=pct(A,a[poz+1],aa,ab,ac);
	ins(A,B,C);
}
void sortare()
{
	double sx=0,sy=0;
	for(int i=1;i<=nr;i++)
	{
		sx+=b[i].x;
		sy+=b[i].y;
	}
	sx/=nr;
	sy/=nr;
	for(int i=1;i<=nr;i++)
	{
		b[i].x-=sx;
		b[i].y-=sy;
	}
	sort(b+1,b+nr+1,cmp);
}
void arie()
{
	nr=0;
	for(int i=1;i<=nrs;i++)
	if(s[i].x==1)
	{
		nr++;
		b[nr]=s[i].y;
	}
	sortare();
	b[nr+1]=b[1];
	double rez=0;
	for(int i=1;i<=nr;i++)
		rez+=det({0,0},b[i],b[i+1]);
	rez/=2;
	rez=abs(rez);
	fout<<fixed<<setprecision(2)<<rez;
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    	fin>>a[i].x>>a[i].y;
    double ar=0;
    a[0]=a[n];
    a[n+1]=a[1];
    for(int i=1;i<=n;i++)
        ar+=det({0,0},a[i],a[i+1]);
    if(ar>0)
        reverse(a+1,a+n+1);
    a[0]=a[n];
    a[n+1]=a[1];
    for(int i=1;i<=n;i++)
    if(det(a[i-1],a[i],a[i+1])<0)
    {
    	ins2(a[i]);
    	for(int j=i+1;j<=n;j++)
            if(det(a[j-1],a[j],a[j+1])<0)
    		sol({a[i],a[i+1]},{a[j],a[j+1]});
    }
    for(int i=1;i<=n;i++)
    if(det(a[i-1],a[i],a[i+1])<0)
    	add(i);
    arie();
}