Cod sursa(job #575383)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 8 aprilie 2011 11:32:18
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<stdio.h>
#include<stdlib.h>
#define N 200010
struct asd{float k;float v;}left[N], right[N];
int i,n,a,b,c,d, leftnr, rightnr, sol;
float MIN;

int cmp(const void *a, const void *b)
{
	return ((asd *)a)->k>((asd *)b)->k;
}

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", &a, &b, &c);
		if(b>c)
			{
				d=b;
				b=c;
				c=d;
			}
		if(a>0)
		{	
		
			right[++rightnr].k=(float)b/a;
			right[rightnr].v=(float)c/a;
		}
		else
		{
			a=-a;
			left[++leftnr].k=(float)b/a;
			left[leftnr].v=(float)c/a;
		}
	}
	right[0].k=-N*N;
	left[0].k=-N*N;
	qsort(right, rightnr+1, sizeof(asd), cmp);
	qsort(left, leftnr+1, sizeof(asd), cmp);
	for(i=1;i<=rightnr;i++)
	{
		MIN=right[i].v;
		sol++;
		for(++i;i<=rightnr&&right[i].k<=MIN;i++)
			if(right[i].v<MIN)
				MIN=right[i].v;
		i--;
	}
	for(i=1;i<=leftnr;i++)
	{
		MIN=left[i].v;
		sol++;
		for(++i;i<=leftnr&&left[i].k<=MIN;i++)
			if(left[i].v<MIN)
				MIN=left[i].v;
		i--;
	}
	printf("%d", sol);
	return 0;
}