Cod sursa(job #197002)

Utilizator gcosminGheorghe Cosmin gcosmin Data 30 iunie 2008 17:52:46
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;

#define MP make_pair
#define ff first
#define ss second

#define NMAX 200010

int N;

const double pi = acos(-1);

vector <pair <double, pair<int, int> > > ev;

vector <int> cur;

char scos[NMAX];

double get_unghi(int x, int y)
{
	double unghi = atan2(y, x);
	if (unghi < 0) unghi += 2 * pi;
	if (unghi > 3 * pi * 0.5) unghi -= 2 * pi;
	return unghi;
}

int main()
{
	int i, x, y1, y2;
	double u1, u2;

	freopen("rays.in", "r", stdin);
	freopen("rays.out", "w", stdout);

	scanf("%d", &N);

	for (i = 1; i <= N; i++) {
		scanf("%d %d %d", &x, &y1, &y2);

		u1 = get_unghi(x, y1);
		u2 = get_unghi(x, y2);

		if (u1 > u2) swap(u1, u2);

		ev.push_back(MP(u1, MP(i,-1)));
		ev.push_back(MP(u2, MP(i, 1)));
	}

	sort(ev.begin(), ev.end());

	int nev = ev.size(), rez = 0;

	for (i = 0; i < nev; i++) {
		if (ev[i].ss.ss == -1) cur.push_back(ev[i].ss.ff);
		else {
			if (scos[ev[i].ss.ff]) continue;

			for (vector <int> :: iterator it = cur.begin(); it != cur.end(); ++it) scos[*it] = 1;
			cur.clear();

			rez++;
		}
	}

	printf("%d\n", rez);

return 0;
}