Pagini recente » Cod sursa (job #80259) | Cod sursa (job #2938393) | Cod sursa (job #457019) | Cod sursa (job #74144) | Cod sursa (job #1127356)
#include <cstdio>
#include <algorithm>
#define Nmax 200005
#define eps 0.0000001
using namespace std;
struct segm
{
double p1,p2;
};
segm a[Nmax],b[Nmax];
int sol,len1,len2;
inline bool Cmp(const segm A, const segm B)
{
if(A.p1==B.p1)
return A.p2<B.p2;
return A.p1<B.p1;
}
inline void Greedy(const segm a[], const int N)
{
int i;
double minim,maxim,st,dr;
++sol;
minim=min(a[1].p1,a[1].p2);
maxim=max(a[1].p1,a[1].p2);
for(i=2;i<=N;++i)
{
st=min(a[i].p1,a[i].p2);
dr=max(a[i].p1,a[i].p2);
if((dr>=minim && st<=maxim))
{
minim=max(minim,st);
maxim=min(maxim,dr);
}
else
{
++sol;
minim=st; maxim=dr;
}
}
}
int main()
{
int i,N,x,y1,y2;
double aux;
freopen ("rays.in","r",stdin);
freopen ("rays.out","w",stdout);
scanf("%d", &N);
for(i=1;i<=N;++i)
{
scanf("%d%d%d", &x,&y1,&y2);
if(x>0)
{
++len1;
a[len1].p1=(double)y1/x;
a[len1].p2=(double)y2/x;
if(a[len1].p1>a[len1].p2)
{
aux=a[len1].p1; a[len1].p1=a[len1].p2; a[len1].p2=aux;
}
}
else
{
++len2;
b[len2].p1=(double)y1/x;
b[len2].p2=(double)y2/x;
if(b[len2].p1>b[len2].p2)
{
aux=b[len2].p1; b[len2].p1=b[len2].p2; b[len2].p2=aux;
}
}
}
sort(a+1,a+len1+1,Cmp);
sort(b+1,b+len2+1,Cmp);
Greedy(a,len1); Greedy(b,len2);
printf("%d\n", sol);
return 0;
}