Cod sursa(job #328845)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 3 iulie 2009 15:20:43
Problema Rays Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <stdio.h>
#include <math.h>
#include <string.h>
#define Nmax 200005

struct trei{
	long x,y1,y2;
};
struct sinuri{
	float sin1,sin2;
};

trei a[Nmax];  // toate segmentele verticale
float v[Nmax];  // pe rand cu x>=0 si x<0 calculez unghiuri fata de ox
 // pun si sin1 si si sin1 si sin2 si sortez
int s12[Nmax*2],use[Nmax*2],nr[Nmax*2];
long n,i,tot=0,z;

void citire(){
	long i;
   freopen("rays.in","r",stdin);
   freopen("rays.out","w",stdout);
   scanf("%ld",&n);
   for(i=1;i<=n;++i) scanf("%ld%ld%ld",&a[i].x,&a[i].y1,&a[i].y2);
}

void baga(long i){ // baga sinusurile
	v[++z] = a[i].y1 / ( sqrt( a[i].x*a[i].x + a[i].y1*a[i].y1) ); // sin1
   s12[z]=1; nr[z]=i;
	v[++z] = a[i].y2 / ( sqrt( a[i].x*a[i].x + a[i].y2*a[i].y2) ); // sin2
   s12[z]=2; nr[z]=i;
   if(v[z]<v[z-1]){
   	float aux=v[z]; v[z]=v[z-1]; v[z-1]=aux;
   }
   // cateta opusa / (ipotenuza = dist x,y1/2 la 0,0)
}

void sort(long l,long r){
	long i,j,aux,s12x;
   float x,y;
   i=l; j=r; x=v[l+(r-l)/2]; s12x=s12[l+(r-l)/2];
   do{
   	while((v[i] < x) ||(v[i]==x && s12[i]<s12x) /*&& i<z*/) ++i;
      while((x < v[j]) ||(x==v[j] && s12x<s12[j]) /*&& j>1*/) --j;
      if(i<=j){
      	y=v[i]; v[i]=v[j]; v[j]=y;
         aux=s12[i]; s12[i]=s12[j]; s12[j]=aux;
         aux=nr[i]; nr[i]=nr[j]; nr[j]=aux;
         ++i; --j;
      }
   } while(i<=j);
   if(i<r) sort(i,r);
   if(l<j) sort(l,j);
}

void work(){
     long z0,zs;
     sort(1,z); // sortez
     z0=1; zs=1;
     while (zs<=z){
        	if(s12[zs]==2 && use[nr[zs]]==0){
         	while(z0<=zs){
            	use[nr[z0]]=1;
               ++z0;
            }
            tot++; // nr total de raze
         }
         zs++;
     }
}

int main(){
	citire();

   for(z=0,i=1;i<=n;++i)
     if(a[i].x<0) baga(i);

   work();

   memset(v,0,sizeof(v));
   memset(use,0,sizeof(use));
   memset(s12,0,sizeof(s12));
   memset(nr,0,sizeof(nr));


   for(z=0,i=1;i<=n;++i)
     if(a[i].x>=0) baga(i);

   work();

   printf("%ld\n",tot);
   fclose(stdin); fclose(stdout);
   return 0;
}

/*

*/