Cod sursa(job #1499996)

Utilizator ArkinyStoica Alex Arkiny Data 11 octombrie 2015 13:42:21
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<fstream>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

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

#define MAX 200001


struct LINE
{
	int x, y1, y2;
};

LINE v[MAX];
int N, m1_l = 0, m2_l = 0,l=0;
double m1_y1[MAX],m1_y2[MAX], m2_y1[MAX],m2_y2[MAX];

bool sort_function_m1_y1(int i, int j) { return (m1_y1[i]<m1_y1[j]); }
bool sort_function_m1_y2(int i,int j){ return (m1_y2[i]<m1_y2[j]); }
bool sort_function_m2_y1(int i, int j) { return (m2_y1[i]<m2_y1[j]); }
bool sort_function_m2_y2(int i, int j) { return (m2_y2[i]<m2_y2[j]); }
int main()
{
	in >> N;
	int x, y1, y2;
	while (in >> x >> y1 >> y2)
	{
		if (x > 0)
		{
			m1_y1[++m1_l] = double(y1) / x;
			m1_y2[m1_l] = double(y2) / x;
		}
		else
		{
			m2_y1[++m2_l] = double(y1) / x;
			m2_y2[m2_l] = double(y2) / x;
		}
		v[++l].x = x;
		v[l].y1 = y1;
		v[l].y2 = y2;
	}
	sort(m1_y1 + 1, m1_y1 + m1_l + 1, sort_function_m1_y1);
	sort(m1_y2 + 1, m1_y2 + m1_l + 1, sort_function_m1_y2);

	sort(m2_y1 + 1, m2_y1 + m2_l + 1, sort_function_m2_y1);
	sort(m2_y2 + 1, m2_y2 + m2_l + 1, sort_function_m2_y2);

	int sol = 0;
	int i=1, j=1;

	while (j <= m1_l)
	{
		if (m1_y1[i] <= m1_y2[j])
		{
			++i;
		}
		else
		{
			++sol;
			++j;
			while (j<=m1_l && m1_y2[j] < m1_y1[i])
				++j;
		}
	}
	i = 1, j = 1;
	while (j <= m2_l)
	{
		if (m2_y1[i] <= m2_y2[j])
		{
			++i;
		}
		else
		{
			++sol;
			++j;
			while (j <= m2_l && m2_y2[j] < m2_y1[i])
				++j;
		}
	}
	out << sol;
	return 0;
}