Cod sursa(job #1493311)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 28 septembrie 2015 23:26:13
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<fstream>
#include<algorithm>

#define x first
#define y1 second.first
#define y2 second.second

#define DIM 200010

using namespace std;

ifstream fin("rays.in");
ofstream fout("rays.out");

int n, nright, nleft;

int sol;

pair<int, pair<int, int> > v[2][DIM];

bool cmp(const pair<int, pair<int, int> > &a, const pair<int, pair<int, int> > &b) {

	return 1LL * a.y2 * b.x < 1LL * a.x * b.y2;

}

void solve(int crt) {

	int n = (crt ? nright : nleft);

	sort(v[crt] + 1, v[crt] + n + 1, cmp);
	
	int xlast = v[crt][1].x;
	int ylast = v[crt][1].y2;
	
	sol++;

	for (int i = 2; i <= n; i++){
	
		if (1LL * v[crt][i].x * ylast < 1LL * v[crt][i].y1 * xlast){
			
			sol++;
			
			xlast = v[crt][i].x;
			ylast = v[crt][i].y2;
		
		}
	
	}

}

int main(){

	fin >> n;

	for (int i = 1; i <= n; i++) {

		pair<int, pair<int, int> > s;

		fin >> s.x >> s.y1 >> s.y2;

		if (s.y1 > s.y2)
			swap(s.y1, s.y2);

		if (s.x < 0) {

			s.x *= (-1);

			v[0][++nleft] = s;

		}
		else {

			v[1][++nright] = s;

		}

	}
	if (nleft)
		solve(0);
	if (nright)
		solve(1);

	fout << sol << "\n";

	return 0;

}

//Miriam e tare!