Cod sursa(job #113368)

Utilizator wefgefAndrei Grigorean wefgef Data 9 decembrie 2007 19:05:00
Problema Rays Scor Ascuns
Compilator cpp Status done
Runda Marime 1.1 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define pb push_back
#define sz(c) int((c).size())
#define all(c) (c).begin(), (c).end()

typedef struct Segment {
	int x, y1, y2;
} Segment;

int ret;
vector<Segment> v, u;

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

	int N;
	for (scanf("%d", &N); N; --N) {
		Segment tmp;
		scanf("%d %d %d", &tmp.x, &tmp.y1, &tmp.y2);

		if (tmp.y1 > tmp.y2) tmp.y1 ^= tmp.y2 ^= tmp.y1 ^= tmp.y2;

		if (tmp.x > 0) v.pb(tmp);
		else {
			tmp.x *= -1;
			u.pb(tmp);
		}
	}
}

int cross(int X1, int Y1, int X2, int Y2) {
	long long P = (long long)X1*Y2 - (long long)X2*Y1;
	if (P == 0) return 0;
	return P > 0 ? 1 : -1;
}

inline int cmp(Segment a, Segment b) {
	return cross(a.x, a.y2, b.x, b.y2) == 1;
}

void Solve(vector<Segment> &v) {
	sort(all(v), cmp);
	if (!sz(v)) return;

	int X = v[0].x;
	int Y = v[0].y2;
	++ret;

	for (int i = 1; i < sz(v); ++i)
		if (cross(X, Y, v[i].x, v[i].y1) == 1) {
			++ret;
			X = v[i].x;
			Y = v[i].y2;
		}
}

int main() {
	ReadData();
	Solve(v);
	Solve(u);
	printf("%d\n", ret);
}