Cod sursa(job #935325)

Utilizator dariusdariusMarian Darius dariusdarius Data 2 aprilie 2013 22:44:39
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
const double eps=1.e-14;
using namespace std;
struct Nod
{
	double a1,a2;
	inline bool operator<(const Nod &other) const
	{
		return a2-other.a2<=-eps;
	}
};
int solve(vector<Nod> &v)
{
	if(v.empty()) return 0;
	//for(int i=0;i<(int)v.size();i++)
	//	fprintf(stderr,"%.3lf %d\n",v[i].a,v[i].tip);
	int ans=1;double R;
	sort(v.begin(),v.end());
	R=v[0].a2;
	for(int i=1;i<(int)v.size();i++)
		if(v[i].a1-R>=eps)
			ans++,R=v[i].a2;
	//for(int i=0;i<(int)v.size();i++)
        //        fprintf(stderr,"%.3lf %.3lf\n",v[i].a1,v[i].a2);
	//fprintf(stderr,"%d\n\n\n",ans);
	return ans;
}
int main()
{
	freopen("rays.in","r",stdin);
	freopen("rays.out","w",stdout);
	int n,x,y1,y2;
	Nod p,q;
	vector<Nod> v1,v2;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&x,&y1,&y2);
		if(y1>y2) swap(y1,y2);
		if(x>0) 
			{
			p.a1=1.0*y1/x;
			p.a2=1.0*y2/x;
			v1.push_back(p);
			}
		else
		{
			p.a1=-1.0*y1/x;
			p.a2=-1.0*y2/x;
			v2.push_back(p);
		}
	}
	printf("%d\n",solve(v1)+solve(v2));
	return 0;
}