Cod sursa(job #324479)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 16 iunie 2009 12:08:42
Problema Rays Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#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;
		}
}