Cod sursa(job #41850)

Utilizator stef2nStefan Istrate stef2n Data 28 martie 2007 17:22:20
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.05 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 poz)
  {
   int i,j;
   bool aux;
   for(i=poz;i<N;i++)
      if(A[i][poz])
        {
         for(j=poz;j<=2*N;j++)
            {
             aux=A[poz][j];
             A[poz][j]=A[i][j];
             A[i][j]=aux;
            }
         return 1;
        }
   return 0;
  }

void modifica_linii(int poz)
  {
   int i,j;
   for(i=poz+1;i<N;i++)
      if(A[i][poz])
        {
         for(j=poz;j<=2*N;j++)
            A[i][j] = A[i][j] ^ A[poz][j];
        }
  }

void Gauss()
  {
   int i,j;
   bool aux;
   for(i=0;i<N-1;i++)
      if(cauta_linie(i))
        modifica_linii(i);
   if(A[N-1][2*N]==false)
     for(i=N-1;i<2*N;i++)
        X[i]=false;
   else
     {
      int gasit=0;
      for(i=N-1;i<2*N;i++)
         if(!A[N-1][i])
           X[i]=false;
         else
           if(!gasit)
             {
              gasit=1;
              X[i]=true;
             }
           else
             X[i]=false;
     }
   for(i=N-2;i>=0;i--)
      {
       aux=false;
       for(j=i+1;j<2*N;j++)
          aux = aux ^ (A[i][j]*X[j]);
       if(!A[i][i])
         if(!A[i][2*N])
           X[i]=aux;
         else
           X[i]=!aux;
       else
         {
          if(A[i][2*N])
            aux=!aux;
          X[i]=aux;
         }
      }
  }


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