Cod sursa(job #827995)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 2 decembrie 2012 21:14:18
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<fstream>
#include<algorithm>
#define dim 200100
#include<cmath>
const double inf = 1LL<<62;
using namespace std;


ifstream f("rays.in");
ofstream g("rays.out");
int n,i,k,K;
double a,b;
struct cub {
	 double st,dr;
}
A[dim],B[dim];
int sol(cub A[],int n){
	
	
	int ans;
	ans=1;
	double val;
	val=-inf;
	
	for(int i=1;i<=n;++i){
		if(A[i].st<=val){// daca intalnim un pct de intrare mai mare decat cel mai mare pct de iesire existent adaugam un glont
			if(A[i].dr<=val)
				val=A[i].dr;
		}
		else{
			++ans;
			val=A[i].dr;
		}
	}
	return ans;
}

struct cmp{
	inline bool operator () ( const interv &a , const interv &b ){
		return a.st < b.st;
	}
};
int main () {
	
	f>>n;
	
	 double  x,y1,y2;
	for(i=1;i<=n;++i){
		f>>x>>y1>>y2;
		if(x>0.0){
			
			a=(double)(y1/x);
			b=(double)(y2/x);
			if(a>b)
				swap(a,b);
			A[++k].st=a;
			A[k].dr=b;
		}
		else {
			a=-(double)(y1/x);
			b=-(double)(y2/x);
			if(a>b)
				swap(a,b);
			
			B[++K].st=a;
			B[K].dr=b;
		}
	}
	//sortam dupa unghi
	sort(A+1,A+1+k,cmp());
	sort(B+1,B+1+K,cmp());
	
	g<<sol(A,k)+sol(B,K);//aplicam greedy
	return 0;
}