Cod sursa(job #116446)

Utilizator tvladTataranu Vlad tvlad Data 18 decembrie 2007 17:23:34
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

struct segment {
	int x, y1, y2;
	double u1,u2;
	bool operator< ( const segment& b ) { return (u1 < b.u1); }
};

vector<segment> sp1, sp2;

int solve ( vector<segment> &v ) {
	sort(v.begin(),v.end());
	int r = 1;
	double p = v[0].u1;
	for (int i = 1; i < v.size(); ++i) {
		if (v[i].u2 > p) {
			++r;
			p = v[i].u1;
		}
	}
	return r;
}

int main() {
	freopen("rays.in","rt",stdin);
	freopen("rays.out","wt",stdout);
	int n = 0;
	scanf("%d",&n);
	for (int i = 0; i<n; ++i) {
		segment a;
		scanf("%d %d %d",&a.x,&a.y1,&a.y2);
		if (a.y1 < a.y2) a.y1 ^= a.y2 ^= a.y1 ^= a.y2;
		a.u1 = (double)a.y1 / fabs((double)a.x);
		a.u2 = (double)a.y2 / fabs((double)a.x);
		if (a.x < 0) sp1.push_back(a); else sp2.push_back(a);
	}
	int r = solve(sp1) + solve(sp2);
	printf("%d\n",r);
}