Cod sursa(job #42281)

Utilizator stef2nStefan Istrate stef2n Data 29 martie 2007 00:50:17
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.96 kb
/*
        Complexitate: O(N^3)
*/

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

#define infile "laser.in"
#define outfile "laser.out"
#define NMAX 514
#define EPS 0.00001
struct segment {int x1,y1,x2,y2; bool stare;};

FILE *fin,*fout;
segment s[NMAX];
int N;

double unghi[2*NMAX],semi[2*NMAX];
bool A[NMAX][2*NMAX],X[2*NMAX];

void read_data()
  {
   fin=fopen(infile,"r");
   fscanf(fin,"%d",&N);
   for(int i=0;i<N;i++)
      fscanf(fin,"%d %d %d %d",&s[i].x1,&s[i].y1,&s[i].x2,&s[i].y2);
   for(int i=0;i<N;i++)
      fscanf(fin,"%d",&s[i].stare);
   fclose(fin);
  }

double unghi_polar(int x, int y)
  {
   double cosinus=fabs(x)/sqrt(x*x+y*y);
   if(x>=0)
     if(y>=0)
       return acos(cosinus);
     else
       return 2*M_PI-acos(cosinus);
   else
     if(y>=0)
       return M_PI-acos(cosinus);
     else
       return M_PI+acos(cosinus);
  }

inline int cmp(double a, double b)
  {
   return a<b;
  }

inline bool find_inters(double &semi, segment &s, double &x, double &y)
  {
   double a1,b1,c1;
   if(fabs(semi-M_PI/2.)<EPS || fabs(semi-3.*M_PI/2.)<EPS)
     {
      a1=1.;
      b1=0.;
      c1=0.;
     }
   else
     {
      a1=tan(semi);
      b1=-1.;
      c1=0.;
     }
   double a2,b2,c2;
   a2=s.y1-s.y2;
   b2=s.x2-s.x1;
   c2=s.x1*s.y2-s.x2*s.y1;
   if(fabs(a2*b1-a1*b2)<EPS)
     return false;
   x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
   y=(a1*c2-a2*c1)/(a2*b1-a1*b2);
   return true;
  }

inline bool intersection(double &semi, segment &s) // verifica daca semidreapta "semi" intersecteaza segmentul "s"
  {
   double x,y,minx,maxx;
   if(!find_inters(semi,s,x,y))
     return false;
   minx=min(s.x1,s.x2);
   maxx=max(s.x1,s.x2);
   if(x<minx || maxx<x)
     return false;
   if(semi<=M_PI/2.)
     return x>=0. && y>=0.;
   if(semi<=M_PI)
     return x<0. && y>=0.;
   if(semi<3.*M_PI/2.)
     return x<0 && y<0;
   return x>=0. && y<0;
  }

inline double mediu(double u, double v)
  {
   double mij;
   u+=2.*M_PI;
   mij=(u+v)/2.;
   if(mij>=2*M_PI)
     mij-=2*M_PI;
   return mij;
  }

void init()
  {
   int i,j;
   for(i=0;i<N;i++)
      {
       unghi[2*i]=unghi_polar(s[i].x1,s[i].y1);
       unghi[2*i+1]=unghi_polar(s[i].x2,s[i].y2);
      }
   sort(unghi,unghi+2*N,cmp);
   for(i=0;i<2*N-1;i++)
      semi[i]=(unghi[i]+unghi[i+1])/2.;
   semi[2*N-1]=mediu(unghi[0],unghi[2*N-1]);
   // in acest moment avem 2*N semidrepte si N segmente
   for(i=0;i<N;i++)
      {
       for(j=0;j<2*N;j++)
          A[i][j]=intersection(semi[j],s[i]);
       A[i][2*N]=s[i].stare;
      }
  }

void write_sol()
  {
   int i,count=0;
   fout=fopen(outfile,"w");
   for(i=0;i<2*N;i++)
      count+=(X[i]==true);
   fprintf(fout,"%d\n",count);
   for(i=0;i<2*N;i++)
      if(X[i])
        fprintf(fout,"%.6lf\n",semi[i]*180./M_PI);
   fclose(fout);
  }

int cauta_linie(int lin, int col)
  {
   bool aux;
   for(int i=lin;i<N;i++)
      if(A[i][col])
        {
         for(int j=col;j<=2*N;j++)
            {
             aux=A[lin][j];
             A[lin][j]=A[i][j];
             A[i][j]=aux;
            }
         return 1;
        }
   return 0;
  }

void Gauss()
  {
   int i,j,k,col=0;

   for(i=0;i<N && col<2*N;i++)
      {
       if(cauta_linie(i,col))
         {
          for(j=i+1;j<N;j++)
             if(A[j][col])
               for(k=col;k<=2*N;k++)
                  A[j][k] = A[i][k] ^ A[j][k];
         }
       else
         {
          X[i]=false;
          i--;
         }
       col++;
      }

   i--;
   col--;
   if(!A[i][2*N])
     for(j=col;j<2*N;j++)
        X[j]=false;
   else
     {
      j=col;
      while(!A[i][j])
           {
            X[j]=false;
            j++;
           }
      X[j]=true;
      for(j++;j<2*N;j++)
         X[j]=false;
     }
   i--;
   while(i>=0)
        {
         while(!A[i][col])
              col--;
         bool aux=false;
         for(j=col+1;j<2*N;j++)
            aux = aux ^ (A[i][j]*X[j]);
         X[i] = aux ^ A[i][2*N];
         i--;
        }
  }


int main()
{
read_data();
init();
Gauss();
write_sol();
return 0;
}