Cod sursa(job #362775)

Utilizator ProtomanAndrei Purice Protoman Data 10 noiembrie 2009 22:24:17
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <algorithm>
#include <stdio.h>
#include <vector>

#define MAX 200010
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

int n, x, y1, y2;
int ap[MAX];
vector <pair <pair <bool, double>, int> > vctPoz, vctNeg;

inline int dr(vector <pair <pair <bool, double>, int> > vctSegm)
{
	int sol = 0;
	vector <int> ret;

	for (int i = 0; i < vctSegm.size(); i++)
		if (ap[i] == 1)
		{
			sol++;
			for (int j = 0; j < ret.size(); j++)
				ap[ret[j]] = 2;
			ret.clear();
		}
		else
		{
			ret.pb(vctSegm[i].s);
			ap[vctSegm[i].s] = 1;
		}

	return sol;
}

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

	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d %d", &x, &y1, &y2);
		if (y1 > y2)
			swap(y1, y2);

		if (x > 0)
		{
			vctPoz.pb(mp(mp(0, y1 / x), i));
			vctPoz.pb(mp(mp(1, y2 / x), i));
		}
		else
		{
			vctNeg.pb(mp(mp(0, y1 / (-x)), i));
			vctNeg.pb(mp(mp(1, y2 / (-x)), i));
		}
	}

	sort(vctPoz.begin(), vctPoz.end());
	sort(vctNeg.begin(), vctNeg.end());

	printf("%d\n", dr(vctPoz) + dr(vctNeg));

	fclose(stdin);
	fclose(stdout);
	return 0;
}