Cod sursa(job #196732)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 28 iunie 2008 14:27:41
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int n, rez, n1, n2;

typedef struct
{
	double x, y;
} interval;
interval a[200005], b[200005];

void swap(int &x, int &y)
{
   int t = x; x = y; y = t;
}

bool operator<(const interval &x, const interval &y)
{
  return x.x < y.x;
}

int main()
{
	freopen("rays.in","r",stdin);
	freopen("rays.out","w",stdout);

	int i, x, y1, y2;
	scanf("%d",&n);

	for (i = 1; i <= n; i++)
	{
		scanf("%d %d %d",&x,&y1,&y2);
		if (y1 > y2) swap(y1,y2);
		if (x > 0)
		{
			a[n1].x = (double) y1 / x;
			a[n1].y = (double) y2 / x;
			n1++;
		}
		else
		{
			x *= (-1);
			b[n2].x = (double) y1 / x;
			b[n2].y = (double) y2 / x;
			n2++;
		}
	} 
	
	std::sort(a, a + n1);

	double xx;

	xx = a[0].y;

	for (i = 1; i < n1; i++)
	{
		if (a[i].x > xx)
		{
		   rez++;
		   xx = a[i].y;
		}
		else if (a[i].y < xx) xx = a[i].y;
	}
	rez++;
	
	std::sort(b, b + n2);

	xx = b[0].y;
	for (i = 1; i < n2; i++)
	{
		if (b[i].x > xx)
		{
		   rez++;
		   xx = b[i].y;
		}
		else if (b[i].y < xx) xx = b[i].y;
	}
	rez++;

	printf("%d\n",rez);
	return 0;
}