Cod sursa(job #115589)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 16 decembrie 2007 18:13:57
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

#define MAXN 200005

int N;

vector< pair< pair<int, int>, int > > v1, v2;
set<int> in; char wasin[MAXN];

inline int cmp( const pair< pair<int, int>, int > &A, const pair< pair<int, int>, int > &B )
{
	long long n1 = (long long)A.first.first * B.first.second;
	long long n2 = (long long)B.first.first * A.first.second;

	if (n1 > n2) return 0;
	if (n1 < n2) return 1;

	//n1 == n2
	return A.second > B.second;
}

inline int solve( const vector< pair< pair<int, int>, int > > &v )
{
	int NR = 0;
	for (size_t k = 0; k < v.size(); k++)
		if (!wasin[ v[k].second ])
			wasin[ v[k].second ] = 1,
			in.insert( v[k].second );
		else
		{
			if (in.find( v[k].second ) == in.end())
				continue;

			NR++; in.clear();
		}
	return NR;
}

int main()
{
	freopen("rays.in", "rt", stdin);
	freopen("rays.out", "wt", stdout);

	scanf("%d", &N);
	v1.clear(); v2.clear();
	for (int i = 1; i <= N; i++)
	{
		int X, Y1, Y2;
		scanf("%d %d %d", &X, &Y1, &Y2);

		if (X >= 0)
			v1.push_back( make_pair( make_pair(Y1, X), i) ),
			v1.push_back( make_pair( make_pair(Y2, X), i) );
		else
			v2.push_back( make_pair( make_pair(Y1, -X), i) ),
			v2.push_back( make_pair( make_pair(Y2, -X), i) );
	}
	sort( v1.begin(), v1.end(), cmp );
	sort( v2.begin(), v2.end(), cmp );

	printf("%d\n", solve(v1) + solve(v2));
	
	return 0;
}