Cod sursa(job #799816)

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

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

int main()
{
	int i;
	double x,ya,yb,dr;
	freopen("rays.in","r",stdin);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lf %lf %lf",&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);
		}
	}
	
	sort(A+1,A+nra+1,Sortare());
	sort(B+1,B+nrb+1,Sortare());
	sol=1;
	dr=A[1].dr;
	for(i=2;i<=nra;i++)
	{
		if(A[i].st>dr)
		{
			sol++;
			dr=A[i].dr;
		}
		else
			dr=min(dr,A[i].dr);
	}
	sol++;
	dr=B[1].dr;
	for(i=2;i<=nrb;i++)
	{
		if(B[i].st>dr)
		{
			sol++;
			dr=B[i].dr;
		}
		else
			dr=min(dr,B[i].dr);
	}
	
	freopen("rays.out","w",stdout);
	printf("%d\n",sol);
	return 0;
}