Mai intai trebuie sa te autentifici.
Cod sursa(job #603121)
Utilizator | 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;
}