Cod sursa(job #115269)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 16 decembrie 2007 11:54:58
Problema Rays Scor 30
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasa a 10-a Marime 1.38 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

#define MAXN 200005
#define EPS 1e-5

int N;
double A1[MAXN], A2[MAXN];

vector< pair<double, int> > v;
set<int> in;

inline int ABS( int X ) { return (X < 0) ? -X : X; }

inline double getAngle( int X, int Y )
{
	double ang = atan2( ABS(Y), ABS(X) );

	if (X >= 0 && Y >= 0) return ang;
	if (X < 0 && Y >= 0) return M_PI - ang;
	if (X < 0 && Y < 0) return M_PI + ang;
	return 2 * M_PI - ang;
}

inline int cmp( const pair< double, int > &A, const pair< double, int > &B )
{
	if (fabs( A.first - B.first ) < EPS)
		return A.second > B.second;

	return A.first < B.first;
}

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

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

		A1[i] = getAngle(Y1, X);
		A2[i] = getAngle(Y2, X);

		if (A1[i] < A2[i])
			v.push_back( make_pair(A1[i], i) ),
			v.push_back( make_pair(A2[i], -i) );
		else
			v.push_back( make_pair(A1[i], -i) ),
			v.push_back( make_pair(A2[i], i) );
	}

	sort( v.begin(), v.end(), cmp );
	in.clear();

	int NR = 0;
	for (size_t k = 0; k < v.size(); k++)
		if (v[k].second > 0)
			in.insert( v[k].second );
		else
		{
			if (in.find( -v[k].second ) == in.end())
				continue;

			NR++; in.clear();
		}

	printf("%d\n", NR);
	
	return 0;
}