Cod sursa(job #123867)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 17 ianuarie 2008 16:32:11
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 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){
    //printf("%.16lf   ",prec*((double)p[*(long*)n1]-p[*(long*)n2]));
     if ((long)((double)prec*((double)p[*(long*)n1]-p[*(long*)n2]))==0){printf("bou");return 0;}
     return ((long)((double)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);
    for (i=1;i<=n;i++)
        printf("%lf %lf\n",p[ind[i]],q[ind[i]]);
    
    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;}
            if (p[ind[j]]<=x[i]&&q[ind[j]]>=x[i]&&q[ind[j]]<=y[i]){y[i]=q[ind[j]];ok=1;}
            if (x[i]<=p[ind[j]]&&p[ind[j]]<=y[i]&&q[ind[j]]>=y[i]){x[i]=p[ind[j]];ok=1;}
            if (p[ind[j]]<=x[i]&&y[i]<=q[ind[j]]){ok=1;}
            if (ok==1)break;
        }
        if (ok==0){f++;x[f]=p[ind[j]];y[f]=q[ind[j]];}
    }
    printf("%ld\n",f);
    
    return 0;
}