Cod sursa(job #951041)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 18 mai 2013 23:39:55
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define x first 
#define y second
using namespace std;
const char iname[] = "rays.in";
const char oname[] = "rays.out";
ifstream fin(iname);
ofstream fout(oname);
int N, i, j, a, b, c, ANS, st, dr;
pair <int,int> P;
struct segment{int xAB, yA, yB; segment(){}; segment(int X, int Y, int Z){xAB = X; yA = Y; yB = Z;}; }D;
vector <segment> Xst, Xdr;
struct cmp{
	bool operator ()(const segment &A, const segment &B) const
	{
		if ((A.yB - P.y) * (B.xAB - P.x) > (A.xAB - P.x) * (B.yB - P.y)) return 1;
		return 0;
	}
};
inline void Solve(vector <segment> v){
	sort (v.begin(), v.end(), cmp());
	if (v.size()){
		++ANS; st = v[0].xAB; dr = v[0].yB;
		for (i = 1; i < v.size(); ++i){
			if (1LL*(st * v[i].yA) > 1LL*(dr * v[i].xAB))
			{
				++ANS;
				st = v[i].xAB; dr = v[i].yB;
			}
		}
	}
}
int main(){
	fin >> N; P.x = P.y = 0;
	while (N--){
		fin >> D.xAB >> D.yA >> D.yB;
		if (D.yA > D.yB) swap(D.yA, D.yB);
		if (D.xAB < 0){
			D.xAB *= -1;
			Xst.push_back(D);
		}
		else
			Xdr.push_back(D);
	}
	Solve(Xst); Solve(Xdr);
	fout << ANS << '\n';
	return 0;
}