Cod sursa(job #809905)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 9 noiembrie 2012 12:49:38
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include<stdio.h>
#include<algorithm>

#define maxn 200005

using namespace std;

FILE*f=fopen("rays.in","r");
FILE*g=fopen("rays.out","w");

const double inf = 1LL<<62;
int n,left,right;

struct interv{
	double a,b;
}L[maxn],R[maxn];

struct cmp{
	inline bool operator () ( const interv &a , const interv &b ){
		return a.a < b.a;
	}
};

inline int solve ( interv *A , int n ){
	
	int r = 0; double right = -inf;
	for ( int i = 1 ; i <= n ; ++i ){
		
		if ( A[i].a <= right){
			if ( A[i].b < right ){
				right = A[i].b;
			}
		}
		else{
			++r;
			right = A[i].b;
		}
	}
	
	return r;
}

int main () {
	
	fscanf(f,"%d",&n);
	int x,y1,y2;
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d %d %d",&x,&y1,&y2);
		if ( y1 > y2 )	swap(y1,y2);
		
		if ( x > 0 ){
			++right;
			R[right].a = (double)y1/x;
			R[right].b = (double)y2/x;
		}
		else{
			++left; x = -x;
			L[left].a = (double)y1/x;
			L[left].b = (double)y2/x;
		}
	}
	
	sort(L+1,L+left+1,cmp());
	sort(R+1,R+right+1,cmp());
	
	int sol = solve(L,left) + solve(R,right);
	fprintf(g,"%d\n",sol);
	
    fclose(f);
    fclose(g);

    return 0;
}