Cod sursa(job #43235)

Utilizator TheCreeepIonita Andrei Lucian TheCreeep Data 29 martie 2007 22:06:34
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.14 kb
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int N;
struct point{
	double x,y;
	int id;
	double a;
};
struct point p[1024];
struct line{
	int p1,p2;
};
struct line dr[512];
	void xchg(int i)
	{
		dr[i].p1=dr[i].p1^dr[i].p2;
		dr[i].p2=dr[i].p1^dr[i].p2;
		dr[i].p1=dr[i].p1^dr[i].p2;
	}
int *mat[512],poz[1024];
void getangle(int i)
	{
		p[i].a=atan2(p[i].y,p[i].x);
		if (p[i].a<0) p[i].a+=2*M_PI;
	}
static int cmp(const void *a, const void *b)
{
	struct point * aa = (struct point*) a;
	struct point * bb = (struct point*) b;
	if (aa->a>bb->a) return 1;
	if (aa->a<bb->a) return -1;
	return 0;
}

int n,x[1024];
void cit()
{
	int i;
	FILE *f=fopen("laser.in","r");
	fscanf(f,"%d",&n);
	for(i=0;i<n;i++) mat[i]=(int*)malloc(sizeof(poz[0])*(2*n+1));
	for(i=0;i<n;i++)			 
	{
		fscanf(f,"%lf %lf %lf %lf",&p[2*i].x,&p[2*i].y,&p[2*i+1].x,&p[2*i+1].y);
		p[2*i].id=2*i;
		p[2*i+1].id=2*i+1;
		dr[i].p1=2*i;
		dr[i].p2=2*i+1;
		getangle(2*i);
		getangle(2*i+1);
	}	
	for(i=0;i<n;i++)
	{
		fscanf(f,"%d",&mat[i][2*n]);
	}
	fclose(f);
}
void substract(int k, int j)
{
	int i;
	for(i=0;i<=2*n;i++)
	{
		mat[k][i]=mat[k][i]-mat[j][i];
		if (mat[k][i]==2 || mat[k][i]==-2) mat[k][i]=0;
	}
	if (mat[k][2*n]==-1) mat[k][2*n]=1;
//	printf("substract %d %d\n",k,j);
}
void invert(int k)
{
	int i;
	for(i=0;i<=2*n;i++) mat[k][i]*=-1;
// 	printf("invert %d\n",k);
}
void printmat()
{
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<=2*n;j++)
			printf("%d ",mat[i][j]);
		printf("\n");
	}
	printf("\n");
}
void solvemat()
{
	int row,col,i,k,j;  
	int *t;
	row=0;
	col=0;
	while (row<n-1 && col <2*n)
	{
		if (mat[row][col]==0)
		{
			for(k=row+1;k<n;k++)
			if (mat[k][col]!=1)
			{
				t=mat[k];
				mat[k]=mat[row];
				mat[row]=t;
				k=n;
//				printf("swap %d %d\n",row,k);
//				printmat();
			}
		}
		if (mat[row][col]==0) 
		{
			col++;
			continue;
		}
		if (mat[row][col]==-1) {invert(row);}
		for(k=row+1;k<n;k++)
			if (mat[k][col]==1) {substract(k,row);}
		
//		printmat();	
		col++;
		row++;
	}	

	for(i=n-1;i>=0;i--)
	{
		k=mat[i][2*n];
		
		for(j=2*n-1;j>=0;j--)
		if (mat[i][j]!=0 && x[j]!=0)
		{
		 	k= k + mat[i][j] * ((x[j]+1)/2);
			if (k==2) k=0;
			if (k==-1) k=1;
//			printf(" + %d %d %d\n",i,j,k);
		}
		
		for(j=2*n-1;j>=0;j--)
		if (mat[i][j]!=0 && x[j]==0)
		{
			x[j] = (2*k-1);
			k=0;
//			printf("x[%d]=%d\n",j,x[j]);
		}
	//	printmat();
	}	
	k=0;
	for(i=0;i<2*n;i++) if (x[i]==1)N++;
}
void rez()
{
	int i,j;
	qsort(p,n*2,sizeof(p[0]),cmp);
	for(i=0;i<2*n;i++)
		poz[p[i].id]=i;	
	
	
	for(i=0;i<n;i++)
	{
		dr[i].p1 = poz[dr[i].p1];
		dr[i].p2 = poz[dr[i].p2];
		
		if ((p[dr[i].p1].a < p[dr[i].p2].a && p[dr[i].p2].a-p[dr[i].p1].a>M_PI) || p[dr[i].p1].a > p[dr[i].p2].a) xchg(i); //in order
		for(j=dr[i].p1;j!=dr[i].p2; j=(j+1)%(2*n))	mat[i][j] = 1;
			
	}
	//printmat();
	solvemat();
}
double computeangle(int i)
{
	double a1 = p[i].a;
	double a2 = p[(i+1)%(2*n)].a;
	if (a1<a2) return (a1+a2)*90/M_PI;
	a1=(a1+a2)/2+M_PI;
	if (a1>=2*M_PI) a1-=M_PI;
	return a1;
}
void scr()
{
	int i;
	FILE *f=fopen("laser.out","w")	;
	fprintf(f,"%d\n",N);
	for(i=0;i<2*n;i++)
	if (x[i]==1)
	{
		fprintf(f,"%lf\n",computeangle(i));
	}
	fclose(f);
}
int main (void)
{
	cit();
	rez();
	scr();
	return 0;
}