Cod sursa(job #753717)

Utilizator geniucosOncescu Costin geniucos Data 30 mai 2012 13:45:52
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int p,i,n,nr,nr1,x[200002],y[200002],l[200002],d[200002];
double maxi;
struct str
{
	double m1,m2;
};
str a[200002];
bool cmp(str a,str b)
{
	return a.m1<b.m1;
}
int main()
{
freopen("rays.in","r",stdin);
freopen("rays.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
	scanf("%d",&x[i]);
	scanf("%d",&y[i]);
	scanf("%d",&l[i]);
	if(x[i]<0)
	{
		x[i]=x[i]*-1;
		nr++;
		a[nr].m1=(double)y[i]/x[i];
		a[nr].m2=(double)(y[i]+l[i])/x[i];
		x[i]=x[i]*-1;
	}
}
sort(a+1,a+nr+1,cmp);
for(i=1;i<=nr;i++)
	if(d[i]==0)
	{
		maxi=a[i].m2;
		d[i]=1;
		p=i+1;
		while(p<=nr)
		{
			if(a[p].m1>maxi) break;
			d[p]++;
			if(a[p].m2>maxi) maxi=a[p].m2;
			p++;
		}
		nr1++;
	}
////////////////////////////////////////////////
nr=0;
for(i=1;i<=n;i++)
	if(x[i]>0)
	{
		nr++;
		a[nr].m1=(double)y[i]/x[i];
		a[nr].m2=(double)(y[i]+l[i])/x[i];
	}
sort(a+1,a+nr+1,cmp);
for(i=1;i<=nr;i++)
	if(d[i]==0)
	{
		maxi=a[i].m2;
		d[i]=1;
		p=i+1;
		while(p<=nr)
		{
			if(a[p].m1>maxi) break;
			d[p]++;
			if(a[p].m2>maxi) maxi=a[p].m2;
			p++;
		}
		nr1++;
	}
printf("%d\n",nr1);
return 0;
}