Cod sursa(job #124259)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 18 ianuarie 2008 18:22:27
Problema Rays Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define prec 300000000

long n,i,j,x11,y11,y22,ind[200002],f,ok;
double p[200002],q[200002],aux,x[200002],y[200002];

int comp1(const void* n1,const void* n2){
     return prec*((double)q[*(long*)n1]-q[*(long*)n2]);
}
int comp2(const void* n1,const void* n2){
     return prec*((double)p[*(long*)n1]-p[*(long*)n2]);
}

int main(){
    freopen("rays.in","r",stdin);
    freopen("rays.out","w",stdout);
    
    scanf("%ld",&n);
    for (i=1;i<=n;i++){
        ind[i]=i;
        scanf ("%ld %ld %ld",&x11,&y11,&y22);
        p[i]=atan2(y11,x11);
        q[i]=atan2(y22,x11);
        if (p[i]>q[i]){aux=p[i];p[i]=q[i];q[i]=aux;}
        //printf("%lf %lf\n",p[i],q[i]);
    }
    p[0]=-4;
    q[0]=-4;
    qsort(ind,n+1,sizeof(long),comp1);
    qsort(ind,n+1,sizeof(long),comp2);
    
    //for (i=1;i<=n;i++)
    //    printf("%lf %lf\n",p[ind[i]],q[ind[i]]);
        
    
    f=0;
    for (j=1;j<=n;j++){
        for (i=1;i<=f;i++){
            ok=0;
            if (x[i]<=p[ind[j]]&&q[ind[j]]<=y[i]){x[i]=p[ind[j]];y[i]=q[ind[j]];ok=1;}
            else
                if (p[ind[j]]<=x[i]&&q[ind[j]]>=x[i]&&q[ind[j]]<=y[i]){y[i]=q[ind[j]];ok=1;}\
                else
                    if (x[i]<=p[ind[j]]&&p[ind[j]]<=y[i]&&q[ind[j]]>=y[i]){x[i]=p[ind[j]];ok=1;}
                    else
                        if (p[ind[j]]<=x[i]&&y[i]<=q[ind[j]]){ok=1;}
                        
            if (ok)break;
        }
        if (!ok){f++;x[f]=p[ind[j]];y[f]=q[ind[j]];}
    }
    
    printf("%ld\n",f);
    
    return 0;
}