Pagini recente » Cod sursa (job #1640453) | Cod sursa (job #2870616) | Cod sursa (job #1483066) | Cod sursa (job #619224) | Cod sursa (job #43235)
Cod sursa(job #43235)
#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;
}