Mai intai trebuie sa te autentifici.

Cod sursa(job #603121)

Utilizator wittinglyQuitee wittingly Data 14 iulie 2011 17:14:30
Problema Rays Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
const int maxn = 200005;
using namespace std;

struct point { 
	int x , y , ind , tip;
};
	
vector < point > neg_points , pos_points;

inline bool cmp ( point A , point B ) {
	return (A.y * B.x) > (A.x * B.y);
}

inline bool cmp2 (point A , point B) { 
	return (A.y * B.x) < (A.x * B.y);
}

int i , j , x , y , y2 , ans , n , first[maxn];

int main()
{
	freopen("rays.in","r",stdin);
	freopen("rays.out","w",stdout);
		
	scanf("%d",&n);
	
	for( i = 1 ; i <= n ; ++i ) { 
		scanf("%d %d %d",&x,&y,&y2);
		
		point up , down;
		
		up.x = x , up.y = y2 , down.x = x , down.y = y;
		up.ind = i , down.ind = i;
		up.tip = 0 , down.tip = 1;
		
		if ( x > 0 ) 
			pos_points.push_back(up) , pos_points.push_back(down);
		else
			neg_points.push_back(up) , neg_points.push_back(down);
	}
	
	sort( pos_points.begin() , pos_points.end() , cmp);
	sort( neg_points.begin() , neg_points.end() , cmp2);
	vector < point > :: iterator it;
	
	memset( first, -1 , sizeof(first));
	int done = -2;
	
	for( it = pos_points.begin() ; it != pos_points.end() ; ++it ) {
		
		point A = *it;
		
		if ( first[ A.ind ] == -1 ) {
			first[ A.ind ] = it - pos_points.begin();
			continue;
		}
		
		if ( first[ A.ind ] <= done ) continue;
		done = it - pos_points.begin();
		
		ans++;
	}
	
	memset( first , -1 , sizeof(first));
	done = -2;
	
	for ( it = neg_points.begin() ; it != neg_points.end() ; ++it ) { 
		
		point A = *it;
		
		if ( first[ A.ind ] == -1 ) {
			first[ A.ind ] = it - neg_points.begin();
			continue;
		}
		
		if ( first[ A.ind ] <= done ) continue;
		done = it - neg_points.begin();
		
		ans++;
	}
	
	printf("%d\n",ans);
	
return 0;
}