Cod sursa(job #1255625)

Utilizator EpictetStamatin Cristian Epictet Data 4 noiembrie 2014 23:37:29
Problema Rays Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("rays.in");
ofstream fout ("rays.out");
typedef struct { int x, y1, y2; } art;
int N, sol;
vector < art > VP, VN;
art aux;

int cmp(art a, art b)
{
	return a.y2 * b.x < a.x * b.y2;
}

void Rezolva(vector < art > &V)
{
	sort (V.begin(), V.end(), cmp);
	if (!V.empty())
	{
		int x = V[0].x;
		int y = V[0].y2;
		sol++;
		for (int i=1; i<V.size(); i++)
		{
			if (y * V[i].x < x * V[i].y1) 
			{
				sol++;
				x = V[i].x;
				y = V[i].y2;
			}
		}
	}
}

int main()
{
	fin >> N;
	for (int i=1; i<=N; i++)
	{
		fin >> aux.x >> aux.y1 >> aux.y2;
		if (aux.y1 > aux.y2) swap(aux.y1, aux.y2);
		if (aux.x > 0)
		{
			VP.push_back(aux);
		}
		else
		{
			aux.x *= -1;
			VN.push_back(aux);
		}
	}
	
	Rezolva(VP);
	Rezolva(VN);
	
	fout << sol << '\n';
	fout.close();
	return 0;
}