Cod sursa(job #238215)

Utilizator alexeiIacob Radu alexei Data 31 decembrie 2008 22:15:48
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
#define NMAX 200002

int X[NMAX],Y1[NMAX],Y2[NMAX],I[NMAX];
bool S[NMAX];
double M[2][NMAX];

inline void swap(const int a)
{
	Y1[a]^=Y2[a];
	Y2[a]^=Y1[a];
	Y1[a]^=Y2[a];
}

inline bool cmp(const int a,const int b)
{
	if( S[a]==S[b] )
	{
		if( M[0][a]==M[0][b] )
			return M[1][a]<M[1][b];
		else
			return M[0][a]<M[0][b];
	}
	else
		return S[a]<S[b];
}

int main()
{
	freopen("rays.in","r",stdin);
	freopen("rays.out","w",stdout);
	
	int N;
	scanf("%d",&N);
	
	int i;
	for(i=1; i<=N; ++i)
	{
		scanf("%d%d%d\n",&X[i],&Y1[i],&Y2[i]);
		
		I[i]=i;
	
		if( X[i]>0 )
		{
			if( Y1[i]>Y2[i] ) 
			swap(i);
			S[i]=1;
		}
		else
		{
			if( Y2[i]>Y1[i] )
			swap(i);
			S[i]=0;
		}
		
		M[0][i]=(double)Y1[i]/X[i];
		M[1][i]=(double)Y2[i]/X[i];	
	}

	sort(I+1,I+1+N,cmp);

	int ANS=0;int a1=1,a2=2;bool prev=1;
	
	for(i=1; i<N; ++i)
	{
		if( prev==true && S[I[i+1]]==1 )
			prev=false,++i;

		a1=I[i];a2=I[i+1];
		
		if( M[0][a1]<=M[0][a2] && M[1][a2]<=M[1][a1] )++ANS;
		else
			if( M[0][a2]<=M[1][a1] && M[1][a2]>=M[1][a1])++ANS,M[1][a2]=M[1][a1];
	
	}

	printf("%d\n",N-ANS);
	return 0;
}