Cod sursa(job #115385)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 16 decembrie 2007 12:29:20
Problema Rays Scor 100
Compilator cpp Status done
Runda preONI 2008, Runda 2, Clasa a 10-a Marime 1.23 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
const int n_max = 200001;
double p[n_max][2];
int c[n_max],
    y1[n_max],
    y2[n_max],
    x[n_max],
    ind[n_max];
int i, n, s, t;
bool cmpf (const int a, const int b)
{
	if (c[a] == c[b])
	{
		if (p[a][0] == p[b][0])
			return (p[a][1]<p[b][1]);
		else
			return (p[a][0] < p[b][0]);
	}
	else
		return (c[a] < c[b]);
}

void solve()
{
	int i, o = 1, k = 2, g=1;
	for (i = 1; i<n; ++ i)
	{
		if (g && c[ind[i+1]] == 2)
		{
			++i;
			g = 0;
		}
		o = ind[i];
		k = ind[i+1];
		if (p[o][0]<=p[k][0] && p[k][1] <= p[o][1])
		{
			++s;
		}
		else
		if (p[k][0] <= p[o][1] && p[k][1] >=p[o][1])
		{
			++s;
			p[k][1] = p[o][1];
			
		}
	}
}

int main()
{
	freopen("rays.in","r",stdin);
	freopen("rays.out","w",stdout);
	scanf("%d", &n);
	for (i = 1; i <=n; ++ i)
	{
		scanf("%d %d %d", &x[i], &y1[i], &y2[i]);
	
		if (x[i]>=0)
		{
			if (y2[i]<y1[i])
			{
				t = y1[i];
				y1[i] = y2[i];
				y2[i] = t;
			}
			c[i] = 2;

		}
		else
		{
			if (y1[i]<y2[i])
			{
				t = y1[i];
				y1[i] = y2[i];
				y2[i] = t;
			}
			c[i] = 1;
		}
		p[i][0] = (double)y1[i]/x[i];
		p[i][1] = (double)y2[i]/x[i];

		ind[i] = i;
	}
	sort(ind +1 , ind + n +1, cmpf);
	solve();	
	printf("%d\n", n-s);
	return 0;
}