Cod sursa(job #138779)

Utilizator MariusMarius Stroe Marius Data 19 februarie 2008 09:45:44
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const char iname[] = "rays.in";
const char oname[] = "rays.out";

#define PB push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++ i)

#define MAXN  200005

struct entry {
	int x, y, index; 
	bool head;

	entry() {}
	entry(int x, int y, int index, bool head)
	{
		this->x = x;
		this->y = y;
		this->index = index;
		this->head = head;
	}
} ;

int n;

vector <entry> A, B;

vector <bool> sel;

stack <int> stk;


bool mycomp(entry a, entry b) {
	return (a.x * b.y - a.y * b.x > 0);
}

int work(vector <entry> &A)
{
	int cnt = 0;

	sort(A.begin(), A.end(), mycomp);

	sel.assign(n, false);

	vector <entry>::iterator i;

	for (i = A.begin(); i != A.end(); ++ i)
	{
		if (sel[(*i).index])
			continue ;

		if ((*i).head == true)
			stk.push((*i).index);
		else {
			while (!stk.empty())
			{
				sel[stk.top()] = true;
				stk.pop();
			}
			cnt ++;
		}
	}

	return cnt;
}


int main(void)
{
	FILE *fi;
	
	int x, y1, y2;

	fi = fopen(iname, "r");
	fscanf(fi, "%d", &n);

	FOR(i, 0, n)
	{
		fscanf(fi, "%d %d %d", &x, &y1, &y2);
		if (x > 0)
			A.PB(entry(x, y1, i, true)), A.PB(entry(x, y2, i, false));
		else {
			x = -x;
			B.PB(entry(x, y1, i, true)), B.PB(entry(x, y2, i, false));
		}
	}

	sel.resize(n);

	fprintf(fopen(oname, "w"), "%d\n", work(A), work(B));

	fcloseall();

	return 0;
}