Cod sursa(job #819913)

Utilizator ChallengeMurtaza Alexandru Challenge Data 19 noiembrie 2012 20:29:53
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const char InFile[]="rays.in";
const char OutFile[]="rays.out";
const int MaxN=200111;
const double PI=3.1415926535897932384626433832795;
const double RAD2DEG=180/PI;
const double INF=1e32;

ifstream fin(InFile);
ofstream fout(OutFile);

struct Inter
{
	Inter(double st=0.0, double dr=0.0):st(st),dr(dr){}

	double st,dr;
};

struct Inter_CMP
{
	inline bool operator() (const Inter &A, const Inter &B)
	{
		return A.st<B.st;
	}
};

int N,sol,done[MaxN],leftYind=-1,rightYind=-1;
int mx,my1,my2;
double st,dr;
Inter leftY[MaxN],rightY[MaxN];

inline void Solve(Inter *V,int length)
{
	sort(V,V+length,Inter_CMP());
	double right=-INF;
	for(register int i=0;i<length;++i)
	{
		if(V[i].st>right)
		{
			++sol;
			right=V[i].dr;
		}
	}
}

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>mx>>my1>>my2;
		st=(double)my1/mx;
		dr=(double)my2/mx;
		if(st>dr)
		{
			swap(st,dr);
		}
		if(mx<0)
		{
			st=-st;
			dr=-dr;
			swap(st,dr);
			leftY[++leftYind]=Inter(st,dr);
		}
		else
		{
			rightY[++rightYind]=Inter(st,dr);
		}
	}
	fin.close();

	Solve(leftY,leftYind+1);
	Solve(rightY,rightYind+1);

	fout<<sol;
	fout.close();
	return 0;
}