Cod sursa(job #493882)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 19 octombrie 2010 19:53:28
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define nmax 400010

struct nr
{
	double v;
	char t;
	int p;
} a[nmax], b[nmax];

int cmp(nr a, nr b)
{
	return a.v>b.v;
}

int n, sol, h, k, q[nmax];
char p[nmax];

int main()
{
	freopen("rays.in","r",stdin);
	freopen("rays.out","w",stdout);
	scanf("%d",&n);
	int i, j;
	double x, y1, y2;
	for (i=1; i<=n; i++) 
	{
		scanf("%lf %lf %lf",&x,&y1,&y2);
		if (y1<y2) swap(y1,y2);
		if (x>0) 
		{
			a[++h].v=y1/x; 
			a[h].t=1;
			a[h].p=i;
			a[++h].v=y2/x;
			a[h].t=2;
			a[h].p=i;
		} else
		{
			x=-x;
			b[++k].v=y1/x;
			b[k].t=1;
			b[k].p=i;
			b[++k].v=y2/x;
			b[k].t=2;
			b[k].p=i;
		}
	}
	sort(a+1, a+h+1, cmp);
	int c=0;
	for (i=1; i<=h; i++)
	{
		if (a[i].t==2 && !p[a[i].p]) 
		{
			if (c) 
			{
				sol++;
				for (j=1; j<=c; j++) p[q[j]]=1;
				c=0;
			}
		} else 
			q[++c]=a[i].p;
	}
	sort(b+1, b+k+1, cmp);
	c=0;
	for (i=1; i<=k; i++)
	{
		if (b[i].t==2 && !p[b[i].p]) 
		{
			if (c) 
			{
				sol++;
				for (j=1; j<=c; j++) p[q[j]]=1;
				c=0;
			}
		} else q[++c]=b[i].p;;
	}
	printf("%d\n",sol);
}