Cod sursa(job #324426)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 16 iunie 2009 09:24:45
Problema Rays Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include<stdio.h>
#define N 200010
#define tip long long
#include<algorithm>
using namespace std;
struct punct{tip x,d,u;};
punct p[N];
int n,m,i,j,sol,D[N],U[N],viz[N],CD(int ii,int jj),CU(int ii,int jj);
void solve1(),solve2(),print();
int main()
{
	solve1();
	solve2();
	print();
	return 0;
}
void solve1()
{
	tip xx,aa,bb;
	freopen("rays.in","r",stdin);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld",&xx,&aa,&bb);
		if(xx>0)
		{
			m++;
			p[m].x=xx;
			p[m].d=aa<bb?aa:bb;
			p[m].u=aa+bb-p[m].d;
			D[m]=m;U[m]=m;
		}
	}
	if(m)
	{
		sort(D+1,D+m+1,CD);
		sort(U+1,U+m+1,CU);
		for(i=1,j=1;j<=m;i++)
		{
			if(viz[U[i]])continue;
			sol++;
			while(j<=m&&p[D[j]].x*p[U[i]].u>=p[U[i]].x*p[D[j]].d){viz[D[j]]=1;j++;}
		}
	}
}
void solve2()
{
	tip xx,aa,bb;
	freopen("rays.in","r",stdin);
	scanf("%d",&n);m=0;
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld",&xx,&aa,&bb);
		if(xx<0)
		{
			m++;
			p[m].x=-xx;
			p[m].d=aa<bb?aa:bb;
			p[m].u=aa+bb-p[m].d;
			D[m]=m;U[m]=m;
		}
	}
	if(m)
	{
		sort(D+1,D+m+1,CD);
		sort(U+1,U+m+1,CU);
		for(i=1;i<=m;i++)viz[i]=0;
		for(i=1,j=1;j<=m;i++)
		{
			if(viz[U[i]])continue;
			sol++;
			while(j<=m&&p[D[j]].x*p[U[i]].u>=p[U[i]].x*p[D[j]].d){viz[D[j]]=1;j++;}
		}
	}
}
int CD(int ii,int jj)
{
	if(p[ii].x*p[jj].d>p[jj].x*p[ii].d)return 1;
	return 0;
}
int CU(int ii,int jj)
{
	if(p[ii].x*p[jj].u>p[jj].x*p[ii].u)return 1;
	return 0;
}
void print()
{
	freopen("rays.out","w",stdout);
	printf("%d\n",sol);
}