Cod sursa(job #938652)

Utilizator EduardGeorgescuGeorgescu Eduard EduardGeorgescu Data 13 aprilie 2013 12:57:22
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<cstdio>
#include<algorithm>
#include<cmath>

#define INFINIT 2000000000

using namespace std;

struct LINII{
	int x,y1,y2;
}v[200010];

struct PANTE{
	double pan1,pan2;
}Panta1[200010],Panta2[200010];

bool MyComp( const PANTE &A , const PANTE &B){
	return A.pan1 < B.pan1;
}
	
int main(){
	
	freopen("rays.in","r",stdin);
	freopen("rays.out","w",stdout);
	
	int N;
	
	scanf("%d" ,&N);
	
	int i;
	
	for ( i = 1 ; i <= N ; i ++){
		scanf("%d%d%d" , &v[i].x , &v[i].y1 , &v[i].y2 );
		if(v[i].y1 > v[i].y2)
			swap(v[i].y1,v[i].y2);
	}
	
	int k1=0,k2=0;
	
	for ( i = 1 ; i <= N ; i ++)
		if( v[i].x < 0 )
		{
			++k1;
			Panta1[k1].pan1 = - (double) v[i].y1 *1.0 / v[i].x ;
			Panta1[k1].pan2 = - (double) v[i].y2 *1.0 / v[i].x ;
		}
		else
		{
			++k2;
			Panta2[k2].pan1 = (double) v[i].y1 *1.0 / v[i].x ;
			Panta2[k2].pan2 = (double) v[i].y2 *1.0 / v[i].x ;
		}
		
	sort ( Panta1 + 1 , Panta1 + k1 + 1 , MyComp );
	sort ( Panta2 + 1 , Panta2 + k2 + 1 , MyComp );
 		
	int nr=2;
	
	double final = Panta1[1].pan2;
	
	for ( i = 2 ; i <= k1 ; i ++ )
		if ( Panta1[i].pan1 > final || Panta1[i].pan2 < final ){
			if ( Panta1[i].pan1 > final )
				nr ++;
			
			final = Panta1[i].pan2;
		}
		
	final = Panta2[1].pan2;
	
	for ( i = 2 ; i <= k2 ; i ++ )
		if ( Panta2[i].pan1 > final || Panta2[i].pan2 < final ){
			if ( Panta2[i].pan1 > final )
				nr ++;
			
			final = Panta2[i].pan2;
		}	
	
	printf("%d" , nr );
		 
	return 0;
}