Cod sursa(job #542131)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 25 februarie 2011 20:22:17
Problema Camera Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 5.75 kb
/*
    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 stergere_duplicati(vector<punct> &fig)
{
	
	vector<punct>::iterator poz = unique(fig.begin(),fig.end());
	fig.resize(poz - fig.begin());
	while ((fig.size() > 0)&&(fig[0] == fig[fig.size()-1]))
		fig.pop_back();
}

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));
	stergere_duplicati(fig);
}

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-1; ++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();
	stergere_duplicati(fig);
	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;
}