Cod sursa(job #39325)

Utilizator unholyfrozenCostea Andrei unholyfrozen Data 26 martie 2007 17:16:35
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.58 kb
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>

#define NMAX 1024
#define ER 0.00001
#define nd(a) (*(t_p *)(a))

typedef struct t_v
{
	int a, b, x, y;
};
typedef struct t_p
{
	int x, y;
};

void read();
void calc(double alfa, int poz);
void gauss();

int cmp(const void *a, const void *b);

int N;
t_v V[NMAX / 2];
t_p P[NMAX];
bool A[NMAX / 2][NMAX], AA[NMAX / 2], temp[NMAX], sol[NMAX];
double angle[NMAX], PI;

int main()
{
	freopen("laser.in", "r", stdin);
     freopen("laser.out", "w", stdout);

     read();
     gauss();
	return 0;
}

void read()
{
	int i;
     double a = 0, b = 0;
	scanf("%d", &N);

     for(i = 0; i < N; i++)
     {
     	scanf("%d%d%d%d", &V[i].a, &V[i].b, &V[i].x, &V[i].y);
		P[2 * i].x = V[i].a, P[2 * i].y = V[i].b;
          P[2 * i + 1].x = V[i].x, P[2 * i + 1].y = V[i].y;
     }
     PI = acos(-1);
     qsort(P, 2 * N, sizeof(t_p), cmp);
     for(i = 0; i < 2 * N; i++)
     {
		if(P[i].x >= 0)
          	if(P[i].y >= 0) (a = atan((double)P[i].y / P[i].x) * 180 / PI);
               else a = 270 + (atan((double)P[i].x / (- P[i].y)) * 180 / PI);
          else if(P[i].y >= 0) a = 90 + (atan((double)(- P[i].x) / P[i].y) * 180 / PI);
          	else a = 180 + (atan((double)P[i].y / P[i].x) * 180 / PI);
		if(i) calc((a + b) / 2, i - 1);
		b = a;
     }
	i = 0;
     if(P[i].x >= 0)
          	if(P[i].y >= 0) (a = atan((double)P[i].y / P[i].x) * 180 / PI);
               else a = 270 + (atan((double)P[i].x / (- P[i].y)) * 180 / PI);
          else if(P[i].y >= 0) a = 90 + (atan((double)(- P[i].x) / P[i].y) * 180 / PI);
          	else a = 180 + (atan((double)P[i].y / P[i].x) * 180 / PI);
    calc((a + b + 360) / 2 >= 360 ? ((a + b + 360) / 2) - 360 : (a + b + 360) / 2, 2 * N - 1);
    
    for(i = 0; i < N; i++)
    scanf("%d", &AA[i]);
}

int cmp(const void *a, const void *b)
{
	int x, y;
     if(nd(a).x >= 0)
     if(nd(a).y >= 0)
     x = 1;
     else x = 4;
     else if(nd(a).y >= 0) x = 2;
     	else x = 3;
     if(nd(b).x >= 0)
     if(nd(b).y >= 0)
     y = 1;
     else y = 4;
     else if(nd(b).y >= 0) y = 2;
     	else y = 3;
	if(x < y) return -1;
     else if(y < x) return 1;
     return (nd(a).x * nd(b).y - nd(a).y * nd(b).x >= 0 ? -1 : 1);
}

void calc(double alfa, int poz)
{
	int i, a, b, x, y;
     double a1, a2, aux;
	angle[poz] = alfa;
     
     for(i = 0; i < N; i++)
     {
     	alfa = angle[poz];
		a = V[i].a, b = V[i].b, x = V[i].x, y = V[i].y;
          if(a >= 0)
          	if(b >= 0) a1 = (atan((double)b / a) * 180 / PI);
               else a1 = 270 + (atan((double)a / (-b)) * 180 / PI);
          else if(b >= 0) a1 = 90 + (atan((double)(- a) / b) * 180 / PI);
          	else a1 = 180 + (atan((double)b / a) * 180 / PI);
          if(x >= 0)
          	if(y >= 0) a2 = (atan((double)y / x) * 180 / PI);
               else a2 = 270 + (atan((double)x / (-y)) * 180 / PI);
          else if(y >= 0) a2 = 90 + (atan((double)(- x) / y) * 180 / PI);
          	else a2 = 180 + (atan((double)y / x) * 180 / PI);
               
		if(a1 > a2) aux = a1, a1 = a2, a2 = aux;
          if(a2 - a1 >= 180) alfa = alfa <= a1 ? alfa + 360 : alfa, a1 += 360, aux = a2, a2 = a1, a1 = aux;

		if((alfa >= a1 - ER && alfa <= a2 + ER))
		A[i][poz] = true;
     }
}

void gauss()
{
	int i, j, z, aux, t, rez = 0, ok;

     for(i = 0, j = 0; i < N && j < 2 * N; j++)
     {
     	if(!A[i][j])
          {
          	for(z = i + 1; z < N; z++)
               if(A[z][j]) break;

               if(z == N)
               {
               sol[j] = true;
               rez++;
               continue;
               }
			memcpy(temp, A[i], 2 * N * sizeof(bool));
               memcpy(A[i], A[z], 2 * N * sizeof(bool));
               memcpy(A[z], temp, 2 * N * sizeof(bool));
               aux = AA[i], AA[i] = AA[z], AA[z] = aux;
          }
          for(z = i + 1; z < N; z++)
          if(A[z][j])
          {
          	for(t = j; t < 2 * N; t++)
               A[z][t] ^= A[i][t];
               AA[z] ^= AA[i];
          }
          i++;
     }
     if(AA[N - 1] == true)
     {
     	sol[j - 1] = true;
          rez++;
          for(z = j; z < 2 * N; z++)
          sol[z] = false;
     }
     for(j -= 2, i -= 2; i >= 0 && j >= 0; j--)
     {
     	while(sol[j] && j >= 0) j--;
          
     	if(!A[i][j]) sol[j] = false;
          else
          {
          	ok = 0;
          	for(z = j + 1; z < 2 * N; z++)
               ok ^= A[i][z] & sol[z];
               ok ^= AA[i];
               if(ok) sol[j] = true, rez++;
               i--;
          }
     }
     printf("%d\n", rez);
     for(i = 0; i < 2 * N; i++)
     if(sol[i] == true)
     printf("%lf\n", angle[i]);
}