Cod sursa(job #733657)

Utilizator danalex97Dan H Alexandru danalex97 Data 12 aprilie 2012 18:18:28
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
/*
#include <fstream>
using namespace std;

ifstream F("rays.in");
ofstream G("rays.out");

#define Lmax 200011
struct Intervall{ int Beg;int End;int Inc; }Inter;

Inter Poz[Lmax],Neg[Lmax];
int Cp,Cn,Sol;

void Push(Inter Int[],int& C,int VBeg,int VEnd,int VInc)
{	Int[++C].Beg=VBeg;
	Int[C].End=VEnd;
	Int[C].Inc=VInc;
}

void inv(Inter Int[],int x)
{
	swap(Int[x].Beg,Int[x].End);
}

void swamp(Inter Int[],int x,int y)
{
	swap(Int[x].Beg,Int[y].Beg);
	swap(Int[x].End,Int[y].End);
	swap(Int[x].Inc,Int[y].Inc);
}

int Poz(Inter Int[],int st,int dr,char Chr)
{
	int xst,xdr;
	xst=0;
	xdr=-1;
	
	while (st<dr)
	{
		bool Cond=0;
		
		switch (Chr)
		{
			case 'E': Cond=Int.End[st]<Int.End[dr];
			case 'B': Cond=Int.Beg[st]<Int.Beg[dr];
			case 'I': Cond=Int.Inc[st]<Int.Inc[dr];
		}
		
		if ( Cond )
			{
				st+=xst;
				dr+=xdr;
			}
		else
		{
			swamp(Int,st,dr);
			xst=1-xst;
			xdr=-1-xdr;
			st+=xst;
			dr+=xdr;
		}
	}
	return st;
}

void Quick(Inter Int[],int st,int dr,char Chr)
{
	int p=Poz(Int,st,dr,Chr);
	if (st<p-1)
		Quick(Int,st,p-1,Chr);
	if (p+1<dr)
		Quick(Int,p+1,dr,Chr);
}

void Solve(Inter Int[],int& C)
{
	Quick(Int,1,C,'E');
	
	bool Ray[C+2];
	for (int i=1;i<=C;++i) 
		Ray[i]=0;
	
	for (int i=1;i<=C;++i)
		if ( !Ray[i] )
		{
			Ray[i]=1;
			++Sol;
			
			for ( int j=i; Int[j].End <= Int[i].Beg && j<=C ; ++j )
				if ( Int[j].Beg >= Int[j].End  )
					Ray[j]=true;
		}
}

void Read()
{
	F>>N;
	for (int i=1;i<=N;++i)
	{
		int B,E,I;
		F>>B>>E>>I;
		if ( I>0 )
		{
			Push(Poz,Cp,B,E,I);
			if ( Poz[Cp].Beg > Poz[Cp].End )
				inv(Poz,Cp);
		}
		else
		{
			Push(Neg,Cn,B,E,I);
			if ( Neg[Cn].Beg > Neg[Cn].End )
				inv(Neg,Cn);
		}
	}
}

int main(void)
{
	Read();
	
	Solve(Poz,Cp);
	Solve(Neg,Cn);

	G<<Sol<<'\n';
	
	F.close();
	G.close();
}

*/

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

#define MAX_N 200005
#define FIN "rays.in"
#define FOUT "rays.out"
#define mp make_pair
#define f first
#define s second

typedef pair<double, double> entry;

int N, na, nb;
entry A[MAX_N], B[MAX_N];

int solve(entry A[], int N)
{
    int i, ret = 1;
    double last;
    
    sort(A, A+N);
    last = A[0].f;
    for (i = 1; i < N; ++i)
        if (last < A[i].s)
        {
            last = A[i].f;
            ++ret;
        }
    return ret;
}

int main(void)
{
    int i, x, y1, y2;
    entry e;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d", &N);
    for (i = 0; i < N; ++i)
    {
        scanf("%d %d %d", &x, &y1, &y2);
        e = mp( atan2(y1, abs(x)), atan2(y2, abs(x)) );
        if (e.f < e.s) swap(e.f, e.s);
        if (x < 0)
            A[na++] = e;
        else
            B[nb++] = e;
    }
    printf("%d\n", solve(A, na)+solve(B, nb));

    return 0;
}