Pagini recente » Cod sursa (job #296547) | Cod sursa (job #731193) | Cod sursa (job #326487) | Cod sursa (job #994415) | Cod sursa (job #330321)
Cod sursa(job #330321)
# include <stdio.h>
# include <stdlib.h>
const long int MAXN=200000;
struct {long int x,y1,y2;} seg[MAXN+1];
typedef struct {double a,b;} SEGMENT;
SEGMENT v[MAXN+1];
long int n,vlen,sol;
int compara_SEGMENT(const void *aa, const void *bb)
{
SEGMENT *a=(SEGMENT*)aa;
SEGMENT *b=(SEGMENT*)bb;
if (a->b<b->b) return -1;
if (a->b>b->b) return 1;
if (a->a<b->a) return -1;
if (a->a>b->a) return -1;
return 0;
}
void citire()
{
FILE *f=fopen("rays.in","r");
fscanf(f,"%ld",&n);
long int i,aux;
for (i=1;i<=n;i++)
{
fscanf(f,"%ld%ld%ld",&seg[i].x,&seg[i].y1,&seg[i].y2);
if (seg[i].y1>seg[i].y2)
{
aux=seg[i].y1;
seg[i].y1=seg[i].y2;
seg[i].y2=aux;
}
}
fclose(f);
}
void scrie(long int sol)
{
FILE *g=fopen("rays.out","w");
fprintf(g,"%ld\n",sol);
fclose(g);
}
void init(long int sens)
{
long int i;
vlen=0;
for (i=1;i<=n;i++)
if (seg[i].x*sens>0)
{
vlen++;
v[vlen].a=(double)seg[i].y1/seg[i].x*sens;
v[vlen].b=(double)seg[i].y2/seg[i].x*sens;
}
qsort(v+1,vlen,sizeof(SEGMENT),compara_SEGMENT);
}
int search(SEGMENT *v, long int li, long int lf, double key)
//cautam un segment care se termina imediat inainte de key
{
if (li>lf) return 0;
long int m=(li+lf)/2;
if (v[m].b<key && v[m+1].b>key) return m;
if (v[m].b>key) return search(v,li,m-1,key);
return search(v,m+1,lf,key);
}
void calculeaza()
{
long int i,count[MAXN+1]={0},x;
count[1]=1;
for (i=2;i<=vlen;i++)
{
x=search(v,1,i-1,v[i].a);
count[i]=1+count[x];
}
sol+=count[vlen];
}
int main()
{
citire();
init(1);
calculeaza();
init(-1);
calculeaza();
scrie(sol);
return 0;
}