Cod sursa(job #799812)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 20 octombrie 2012 09:53:48
Problema Rays Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<fstream>
#include<algorithm>
#include<cmath>
using namespace std;
int n,nra,nrb,sol;
struct Interval{double st,dr;};
Interval A[200100],B[200100];

inline bool Sortare(Interval A,Interval B)
{
	return A.st<B.st;
}

int main()
{
	int i;
	double x,ya,yb;
	Interval minim;
	ifstream fin("rays.in");
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>x>>ya>>yb;
		if(x>0.0)
		{
			nra++;
			A[nra].st=atan2(ya,x);
			A[nra].dr=atan2(yb,x);
			if(A[nra].st>A[nra].dr)
				swap(A[nra].st,A[nra].dr);
		}
		else
		{
			nrb++;
			B[nrb].st=atan2(ya,-x);
			B[nrb].dr=atan2(yb,-x);
			if(B[nrb].st>B[nrb].dr)
				swap(B[nrb].st,B[nrb].dr);
		}
	}
	fin.close();
	
	sort(A+1,A+nra+1,Sortare);
	sort(B+1,B+nrb+1,Sortare);
	sol=1;
	minim=A[1];
	for(i=2;i<=nra;i++)
	{
		if(A[i].st>minim.dr)
		{
			sol++;
			minim=A[i];
		}
		else
		{
			minim.st=A[i].st;
			minim.dr=min(minim.dr,A[i].dr);
		}
	}
	sol++;
	minim=B[1];
	for(i=2;i<=nrb;i++)
	{
		if(B[i].st>minim.dr)
		{
			sol++;
			minim=B[i];
		}
		else
		{
			minim.st=B[i].st;
			minim.dr=min(minim.dr,B[i].dr);
		}
	}
	
	ofstream fout("rays.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}