Cod sursa(job #819877)

Utilizator ChallengeMurtaza Alexandru Challenge Data 19 noiembrie 2012 20:01:35
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 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;

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

struct Event
{
	Event(double time=0.0, int type=0):time(time),type(type){}

	double time;
	int type;
};

struct Event_CMP
{
	inline bool operator() (const Event &A, const Event &B)
	{
		if(A.time==B.time)
		{
			return A.type>B.type;
		}
		return A.time<B.time;
	}
};

int N,sol,done[MaxN];
double mx,my1,my2,st,dr;
vector<Event> leftY;
vector<Event> rightY;

inline double GetAngle(double x, double y)
{
	double angle=atan2(y,x);
	angle*=RAD2DEG;
	if(angle<0)
	{
		angle+=360.0;
	}
	angle-=90.0;
	if(angle<0)
	{
		angle+=360.0;
	}
	return angle;
}

inline void Solve(vector<Event> &V)
{
	sort(V.begin(),V.end(),Event_CMP());
	int last=-1;
	for(vector<Event>::iterator it=V.begin();it!=V.end();++it)
	{
		if(last==-1)
		{
			if(it->type>0)
			{
				++sol;
				last=it->type;
			}
		}
		else if(-last==it->type)
		{
			last=-1;
		}
	}
}

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

	Solve(leftY);
	Solve(rightY);

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