Cod sursa(job #37993)

Utilizator stef2nStefan Istrate stef2n Data 25 martie 2007 13:14:25
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;

#include <stdlib.h>
#define infile "laser.in"
#define outfile "laser.out"
#define NMAX 515
struct segment{int x1,y1,x2,y2;};

FILE *fin,*fout;
int n;
segment s[NMAX];
double unghi[2*NMAX]; int ind;
double semi[2*NMAX];
short int stare[NMAX];
int inters[2*NMAX][NMAX];
int st[100];

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

inline double unghi_polar(int x, int y)
  {
   double cosinus=fabs(x)/sqrt((double)x*x+(double)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;
  }

int se_inters(segment s, double a, double b, double c)
  {
   return (a*s.x1+b*s.y1+c)*(a*s.x2+b*s.y2+c)<0.;
  }

inline double mind(double x, double y)
  {
   return (x<y)?x:y;
  }

inline double maxd(double x, double y)
  {
   return (x>y)?x:y;
  }

int ok(segment s, double a1, double b1, double c1, double unghi)
  {
   double a2=s.y1-s.y2;
   double b2=s.x2-s.x1;
   double c2=s.x1*s.y2-s.x2*s.y1;
   double x,y;
   y=(a1*c2-a2*c1)/(a2*b1-a1*b2);
   x=(b1*c2-b2*c1)/(a1*b2-a2*b1);
   if(x<mind(s.x1,s.x2) || x>maxd(s.x1,s.x2))
     return 0;
   if(unghi<=M_PI/2.)
     return x>=0. && y>=0.;
   if(unghi<=M_PI)
     return x<0. && y>=0.;
   if(unghi<=3.*M_PI/2.)
     return x<0. && y<0.;
   return x>=0. && y<0.;
  }

void init()
  {
   int i;
   ind=0;
   for(i=0;i<n;i++)
      {
       unghi[ind++]=unghi_polar(s[i].x1,s[i].y1);
       unghi[ind++]=unghi_polar(s[i].x2,s[i].y2);
      }
   sort(unghi,unghi+ind,cmp);
   for(i=1;i<ind;i++)
      semi[i-1]=(unghi[i-1]+unghi[i])/2.;
   semi[ind-1]=(semi[ind-1]+semi[0])/2.;
   for(i=0;i<ind;i++)
      {
       inters[i][0]=0;
       for(int j=0;j<n;j++)
          if(se_inters(s[j],tan(semi[i]),-1.,0.) && ok(s[j],tan(semi[i]),-1,0,semi[i]))
            inters[i][++inters[i][0]]=j;
      }
  }

double conv(double  i)
  {
   return i*180./M_PI;
  }

void scrie_sol()
  {
   int i,count=0;;
   for(i=0;i<ind;i++)
      if(st[i])
        count++;
   fout=fopen(outfile,"w");
   fprintf(fout,"%d\n",count);
   for(i=0;i<ind;i++)
      if(st[i])
        fprintf(fout,"%.6lf\n",conv(semi[i]));
   fclose(fout);
   exit(0);
  }

void back(int k)
  {
   if(k==ind)
     {
      // verif
      int i,aux[NMAX];
      for(i=0;i<n;i++)
         aux[i]=stare[i];
      for(i=0;i<k;i++)
         if(st[i])
           {
            for(int j=0;j<inters[i][0];j++)
               aux[inters[i][j]]=!aux[inters[i][j]];
           }
      for(i=0;i<n;i++)
         if(!aux[i])
           return;
      scrie_sol();
     }
   st[k]=0;
   back(k+1);
   st[k]=1;
   back(k+1);
  }



int main()
{
citire();
init();
back(0);


return 0;
}