Pagini recente » Cod sursa (job #2900985) | Cod sursa (job #2793003) | Cod sursa (job #53028) | Cod sursa (job #1398991) | Cod sursa (job #115654)
Cod sursa(job #115654)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define node pair< pair<int,int>, pair<int,int> >
#define MN 201222
int N, mx[MN], my1[MN], my2[MN], NE, was[MN];
node ev[2*MN];
bool cmp( node e1, node e2 )
{
double val = atan2( 1.0 * e1.first.second, e1.first.first ) -
atan2( 1.0 * e2.first.second, e2.first.first );
if( abs(val) > 1e-9 )
return val <= 0.0;
return e1.second.first < e2.second.first;
}
int main()
{
freopen("rays.in", "r", stdin);
freopen("rays.out", "w", stdout);
scanf("%d", &N);
for( int i = 1; i <= N; ++i )
{
scanf("%d %d %d", mx + i, my1 + i, my2 + i );
node e1 = make_pair( make_pair(mx[i],my1[i]), make_pair(-1,i) );
node e2 = make_pair( make_pair(mx[i],my2[i]), make_pair( 1,i) );
if( cmp(e2,e1) )
e1.second.first = 1,
e2.second.first = -1;
ev[NE++] = e1, ev[NE++] = e2;
}
sort( ev, ev + NE, cmp );
int last = NE + 1, ret = 0;
// for( int i = 0; i < NE; ++i )
// printf("%d,%d\n", ev[i].first.first, ev[i].first.second );
for( int i = 0; i < NE; ++i )
{
pair<int,int> state = ev[i].second;
// printf("-> %d %d\n", state.second, state.first );
if( state.first == -1 )
{
was[ state.second ] = i;
}
else
{
if( was[ state.second ] >= last );
else{ ++ret, last = i; }
}
}
printf("%d\n", ret);
return 0;
}