Pagini recente » Cod sursa (job #274227) | Cod sursa (job #491708) | Cod sursa (job #2437370) | Cod sursa (job #1365420) | Cod sursa (job #324479)
Cod sursa(job #324479)
#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)(100000000*u1);
u2=atan2(bb,xx);uu2=(int)(100000000*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;
}
}