Pagini recente » Cod sursa (job #219990) | Cod sursa (job #325687) | Cod sursa (job #2335611) | Cod sursa (job #1892639) | Cod sursa (job #124266)
Cod sursa(job #124266)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define prec 300000000
long n,i,j,x11,y11,y22,ind[200002],f,ok;
double a,b,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;
a=p[ind[j]];
b=q[ind[j]];
if (x[i]<=a&&b<=y[i]){x[i]=a;y[i]=b;ok=1;}
else
if (a<=x[i]&&b>=x[i]&&b<=y[i]){y[i]=b;ok=1;}
else
if (x[i]<=a&&a<=y[i]&&b>=y[i]){x[i]=a;ok=1;}
else
if (a<=x[i]&&y[i]<=b){ok=1;}
if (ok)break;
}
if (!ok){f++;x[f]=p[ind[j]];y[f]=q[ind[j]];}
}
printf("%ld\n",f);
return 0;
}