Pagini recente » Cod sursa (job #594068) | Cod sursa (job #761258) | Cod sursa (job #1254891) | Cod sursa (job #2225240) | Cod sursa (job #124259)
Cod sursa(job #124259)
#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;
}