Pagini recente » Cod sursa (job #1363017) | Cod sursa (job #3209701) | Cod sursa (job #2063917) | Cod sursa (job #874304) | Cod sursa (job #324480)
Cod sursa(job #324480)
#include<stdio.h>
#include<math.h>
#include<vector>
#include<utility>
#define N 200010
#include<algorithm>
using namespace std;
pair< int, pair< char,int> > p[N<<1];
int co[N],viz[N],top,sol,n,m,i,r;
void read(),solve();
int main()
{
read();
solve();
printf("%d\n",sol);
return 0;
}
void read()
{
double xx,aa,bb,u1,u2;
int uu1,uu2;
freopen("rays.in","r",stdin);
freopen("rays.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&xx,&aa,&bb);
u1=atan2(aa,xx);uu1=(int)(10000000*u1);
u2=atan2(bb,xx);uu2=(int)(10000000*u2);
p[++m].first=(uu1<uu2)?uu1:uu2;p[m].second.first=0;p[m].second.second=i;
p[++m].first=(uu1<uu2)?uu2:uu1;p[m].second.first=1;p[m].second.second=i;
}
}
void solve()
{
sort(p+1,p+m+1);r=n;
for(i=1;i<=m;i++)
if(!viz[p[i].second.second])
{
if(p[i].second.first)
{
sol++;r-=top;if(!r)return;
while(top)viz[co[top--]]=1;
}
else co[++top]=p[i].second.second;
}
}