Cod sursa(job #196731)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 28 iunie 2008 14:25:01
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 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], c[200005];

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

void bublesort(int x)
{
   int i, ok = 1;
   interval aux;
   while (ok)
   {
     ok = 0;
     for (i = 1; i < x; i++)
	if (c[i].x < c[i-1].x)
	{
	   aux = c[i];
	   c[i] = c[i -1];
	   c[i - 1] = aux;
	   ok = 1;
	}
   }
}

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++;
		}
	}
 
	for (i = 0; i < n1; i++) c[i] = a[i];
	std::sort(c, c+n1);

	double xx;

	xx = c[0].y;

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

	for (i = 0; i < n2; i++) c[i] = b[i];
	std::sort(c, c+n2);

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

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