Cod sursa(job #42607)

Utilizator stef2nStefan Istrate stef2n Data 29 martie 2007 12:54:16
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.87 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 modifica_linii(int lin, int col)
  {
   for(int i=lin+1;i<N;i++)
      if(A[i][col])
        for(int j=col;j<=2*N;j++)
           A[i][j] = A[i][j] ^ A[lin][j];
  }

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


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