Cod sursa(job #600757)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 3 iulie 2011 00:00:18
Problema Camera Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.16 kb
#include<stdio.h>

#define maxN 4105
#define INF 1LL<<60
#define eps 1e-6

FILE*f=fopen("camera.in","r");
FILE*g=fopen("camera.out","w");

int i,d1,d2; double xmin,ymin,xmax,ymax,xint,yint;
double x1,y1,x2,y2,A;

struct poligon{
	int nrvf;
	double x[maxN];
	double y[maxN];
	poligon () {
		nrvf = 0;
	}
}init,v;
	
inline double Abs ( double j ){
	if ( j < 0 )
		return -j;
	return j;
}

inline bool equal ( double a, double b ){
	if ( Abs(a - b) < eps )
		return 1;
	return 0;
}

inline void citire () {
	
	fscanf(f,"%d",&init.nrvf); xmin = ymin = INF; xmax = ymax = -INF;
	
	for ( i = 1 ; i <= init.nrvf ; ++i ){
		fscanf(f,"%lf %lf",&init.x[i],&init.y[i]);
		if ( init.x[i] > xmax )
			xmax = init.x[i];
		if ( init.x[i] < xmin )
			xmin = init.x[i];
		if ( init.y[i] > ymax )
			ymax = init.y[i];
		if ( init.y[i] < ymin )
			ymin = init.y[i];
	}
}

inline void init_v () {
	
	v.nrvf = 4; 
	v.x[1] = xmin; v.y[1] = ymin; 
	v.x[2] = xmin; v.y[2] = ymax; 
	v.x[3] = xmax; v.y[3] = ymax; 
	v.x[4] = xmax; v.y[4] = ymin;
}

inline void swap ( double &a, double &b ){
	double aux = a;
	a = b;
	b = aux;
}

inline int det ( double x1, double y1, double x2, double y2 , double x3, double y3 ){
	
	double d = (x1-x3)*(y2-y3) + (y1-y3)*(x3-x2);
	if ( equal(d,0) )	return 0;
	if ( d > 0 ) return 1;
	return -1;
}

inline void verif_order () {
	int change = 0,i = 1,d;
	
	while ( 1 && i <= (init.nrvf>>1) + 1 ){
		d = det(init.x[1+i],init.y[1+i],init.x[1],init.y[1],init.x[init.nrvf-i+1],init.y[init.nrvf-i+1]);
		++i;
		if ( d != 0 ){
			if ( d == -1 )
				change = 1;
			break ;
		}
	}
	
	if ( change ){
		for ( i = 2 ; i <= (init.nrvf>>1) + 1 ; ++i ){
			swap(init.x[i],init.x[init.nrvf-i+2]);
			swap(init.y[i],init.y[init.nrvf-i+2]);
		}
	}
}

inline void pct_inters ( double x1, double y1, double x2,double y2, double x3,double y3,double x4, double y4 ){
	
	double a1,b1,c1,a2,b2,c2;
	a1 = y2 - y1; b1 = x1 - x2; c1 = x2*y1 - x1*y2;
	a2 = y4 - y3; b2 = x3 - x4; c2 = x4*y3 - x3*y4;
	
	xint = (c2 * b1 - b2 * c1) / (b2 * a1 - b1 * a2);
	if ( !equal(b1,0) )
		yint = (-c1 - a1 * xint) / b1;
	else
		yint = (-c2 - a2 * xint) / b2;
	if ( equal(a1,0) && equal(b2,0) ){
		xint = x3; yint = y1;
	}
	if ( equal(a2,0) && equal(b1,0) ){
		xint = x1; yint = y3;
	}
}

inline poligon cut (){
	
	x1 = init.x[i],y1 = init.y[i],x2 = init.x[i+1],y2 = init.y[i+1];
	int i; poligon new_v; v.x[v.nrvf+1] = v.x[1]; v.y[v.nrvf+1] = v.y[1];
	
	for ( i = 1 ; i <= v.nrvf ; ++i ){
		d1 = -det(x1,y1,x2,y2,v.x[i],v.y[i]);
		d2 = -det(x1,y1,x2,y2,v.x[i+1],v.y[i+1]);
		
		if ( d1 != 0 && d2 != 0 ){
			if ( d1 == 1 && d2 == 1 ){
				++new_v.nrvf; new_v.x[new_v.nrvf] = v.x[i]; new_v.y[new_v.nrvf] = v.y[i];
			}
			if ( d1 == 1 && d2 == -1 ){
				pct_inters(v.x[i],v.y[i],v.x[i+1],v.y[i+1],x1,y1,x2,y2);
				++new_v.nrvf; new_v.x[new_v.nrvf] = v.x[i]; new_v.y[new_v.nrvf] = v.y[i];
				++new_v.nrvf; new_v.x[new_v.nrvf] = xint; new_v.y[new_v.nrvf] = yint;
			}
			if ( d1 == -1 && d2 == 1 ){
				pct_inters(v.x[i],v.y[i],v.x[i+1],v.y[i+1],x1,y1,x2,y2);
				++new_v.nrvf; new_v.x[new_v.nrvf] = xint; new_v.y[new_v.nrvf] = yint;
			}
		}
		else{
			if ( !d1 ){
				++new_v.nrvf; new_v.x[new_v.nrvf] = v.x[i]; new_v.y[new_v.nrvf] = v.y[i];
			}
			if ( !d2 && d1 ){
				++new_v.nrvf; new_v.x[new_v.nrvf] = v.x[i]; new_v.y[new_v.nrvf] = v.y[i];
			}
			if ( !d1 && !d2 ){
				++new_v.nrvf; new_v.x[new_v.nrvf] = v.x[i]; new_v.y[new_v.nrvf] = v.y[i];
			}
		}
	}
	
	return new_v;
}

inline double surface ( double x1, double y1, double x2, double y2 , double x3, double y3 ){
	double d = (x1-x3)*(y2-y3) + (y1-y3)*(x3-x2);
	d = Abs(d) / 2;
	return d;
}

inline void calculate_surface () {
	
	for ( i = 2 ; i < v.nrvf ; ++i ){
		A += surface(v.x[1],v.y[1],v.x[i],v.y[i],v.x[i+1],v.y[i+1]);
	}
}

inline void solve () {
	
	init.x[init.nrvf+1] = init.x[1]; init.y[init.nrvf+1] = init.y[1];
	
	for ( i = 1 ; i <= init.nrvf ; ++i ){
		v = cut();
	}
	
	calculate_surface();
	
	fprintf(g,"%.2lf\n",A);
}
	
int main () {
	
	citire();
	init_v();
	verif_order();
	solve();
	
	fclose(f);
	fclose(g);
	
	return 0;
}