Cod sursa(job #324492)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 16 iunie 2009 12:33:26
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<stdio.h>
#include<math.h>
#include<vector>
#include<utility>
#define N 200010
#include<algorithm>
using namespace std;
pair< long long, 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()
{
	long long xx,aa,bb,pr=1000000000,oo;
	oo=pr*pr;
	freopen("rays.in","r",stdin);
	freopen("rays.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld",&xx,&aa,&bb);aa*=pr;bb*=pr;aa/=xx;bb/=xx;
		if(xx<0){aa+=oo;bb+=oo;}
		p[++m].first=(aa<bb)?aa:bb;p[m].second.first=0;p[m].second.second=i;
		p[++m].first=(aa>bb)?aa:bb;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;
		}
}