Cod sursa(job #272313)

Utilizator stefysStefan stefys Data 6 martie 2009 20:02:34
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const unsigned int MAXN = 200000;
struct Dr { double m1,m2; };

unsigned int num_intervale (Dr const d[], unsigned int s);
bool endslopecomp (Dr const &d1, Dr const &d2);

int main ()
{
	Dr *stanga, *dreapta;
	freopen("rays.in", "r", stdin);
	freopen("rays.out", "w+", stdout);
	unsigned int N, i, stanga_size=0, dreapta_size=0;
	int x,y1,y2;
	scanf("%u", &N);
	stanga = new Dr[N]; dreapta = new Dr[N];
	for (i=0; i<N; ++i) {
		scanf("%d %d %d", &x, &y1, &y2);
		if (x < 0) {
			stanga[stanga_size  ].m1 = -y1/x;
			stanga[stanga_size++].m2 = -y2/x;
		}
		else {
			dreapta[dreapta_size  ].m1 = y1/x;
			dreapta[dreapta_size++].m2 = y2/x;
		}
	}
	sort(stanga, stanga+stanga_size, endslopecomp);
	sort(dreapta, dreapta+dreapta_size, endslopecomp);
	printf("%u\n", num_intervale(stanga, stanga_size)+num_intervale(dreapta,dreapta_size));
	return 0;
}

unsigned int num_intervale (Dr const d[], unsigned int s)
{
	unsigned int ret=1;
	for (unsigned int i=1; i<s; ++i)
		if (d[i].m1 > d[i-1].m2) ++ret;
	return ret;
}

bool endslopecomp (Dr const &d1, Dr const &d2)
{
	return d1.m2 < d2.m2;
}