Cod sursa(job #324423)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 16 iunie 2009 09:11:25
Problema Rays Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 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),ODU(int jj,int ii);
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;
		}
	}
	sort(D+1,D+m+1,CD);
	sort(U+1,U+m+1,CU);
	for(i=1,j=1;i<=m;i++)
	{
		if(viz[U[i]])continue;
		sol++;
		while(ODU(j,i)&&j<=m){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;
		}
	}
	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;i<=m;i++)
	{
		if(viz[U[i]])continue;
		sol++;
		while(ODU(j,i)&&j<=m){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;
}
int ODU(int jj,int ii)
{
	if(p[D[jj]].x*p[U[ii]].u>=p[U[ii]].x*p[D[jj]].d)return 1;
	return 0;
}
void print()
{
	freopen("rays.out","w",stdout);
	printf("%d\n",sol);
}