Pagini recente » Cod sursa (job #208517) | Cod sursa (job #2036732) | Istoria paginii runda/lasm-baraj3-cl11-12 | Cod sursa (job #1684037) | Cod sursa (job #328844)
Cod sursa(job #328844)
#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;
}
/*
*/