Cod sursa(job #818883)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 18 noiembrie 2012 10:59:35
Problema Rays Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<fstream>
#include<algorithm>
#define dim 200100
#include<cmath>
using namespace std;


ifstream f("rays.in");
ofstream g("rays.out");
int n,i,k,K;
double a,b;
struct cub {
	long double st,dr;
}
A[dim],B[dim];
int sol(cub A[],int n){
	
	
	int ans;
	long double val;
	ans=1;
	val=A[1].dr;
	
	for(int i=2;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
			
			ans++;
			val=A[i].dr;
		}
		else
			if(val>A[i].dr)
				val=A[i].dr;
	}
	return ans;
}

int  cmp(cub a,cub b){
	return a.st<b.st;
}
int main () {
	
	f>>n;
	
	long double  x,y1,y2;
	for(i=1;i<=n;++i){
		f>>x>>y1>>y2;
		if(x>0.0){
			
			a=atan2(y1,x);
			b=atan2(y2,x);
			if(a>b)
				swap(a,b);
			A[++k].st=a;
			A[k].dr=b;
		}
		else {
			a=atan2(y1,-x);
			b=atan2(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;
}