Cod sursa(job #330335)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 9 iulie 2009 16:45:59
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
# include <stdio.h>
# include <stdlib.h>

const long int MAXN=200000;

struct {long int x,y1,y2;} seg[MAXN+1];

typedef struct FRACTIE{long int m,n;};
typedef struct {FRACTIE a,b;} SEGMENT;

SEGMENT v[MAXN+1];
long int n,vlen,sol;

int compara_FRACTIE(FRACTIE a, FRACTIE b)
{
    long long f1=(long long)a.m*b.n;
    long long f2=(long long)a.n*b.m;
    if (f1<f2) return -1;
    if (f1>f2) return 1;
    return 0;
}

int compara_SEGMENT(const void *aa, const void *bb)
{
    SEGMENT *a=(SEGMENT*)aa;
    SEGMENT *b=(SEGMENT*)bb;
    if (compara_FRACTIE(a->b,b->b)==-1) return -1;
    if (compara_FRACTIE(a->b,b->b)== 1) return  1;
    if (compara_FRACTIE(a->a,b->a)==-1) return -1;
    if (compara_FRACTIE(a->a,b->a)== 1) 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.m=seg[i].y1;v[vlen].a.n=seg[i].x*sens;
            v[vlen].b.m=seg[i].y2;v[vlen].b.n=seg[i].x*sens;
            }
     qsort(v+1,vlen,sizeof(SEGMENT),compara_SEGMENT);
}

int search(SEGMENT *v, long int lif, long int li, long int lf, FRACTIE key)
//cautam un segment care se termina imediat inainte de key
{
         if (li>lf) return lif-1;
         long int m=(li+lf)/2;
         if (compara_FRACTIE(v[m].b,key)==-1 && compara_FRACTIE(v[m+1].b,key)>=0) return m;
         if (compara_FRACTIE(v[m].b,key)>=0) return search(v,lif,li,m-1,key);
         return search(v,lif,m+1,lf,key);
}
         

void calculeaza()
{
     long int i,count[MAXN+1]={0},x=0;
     count[1]=1;
     for (i=2;i<=vlen;i++)
         {
         x=search(v,x+1,x+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;
}