Pagini recente » Cod sursa (job #1590529) | Cod sursa (job #2098389) | Cod sursa (job #912696) | Cod sursa (job #2331103) | Cod sursa (job #115269)
Cod sursa(job #115269)
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define MAXN 200005
#define EPS 1e-5
int N;
double A1[MAXN], A2[MAXN];
vector< pair<double, int> > v;
set<int> in;
inline int ABS( int X ) { return (X < 0) ? -X : X; }
inline double getAngle( int X, int Y )
{
double ang = atan2( ABS(Y), ABS(X) );
if (X >= 0 && Y >= 0) return ang;
if (X < 0 && Y >= 0) return M_PI - ang;
if (X < 0 && Y < 0) return M_PI + ang;
return 2 * M_PI - ang;
}
inline int cmp( const pair< double, int > &A, const pair< double, int > &B )
{
if (fabs( A.first - B.first ) < EPS)
return A.second > B.second;
return A.first < B.first;
}
int main()
{
freopen("rays.in", "rt", stdin);
freopen("rays.out", "wt", stdout);
scanf("%d", &N);
v.clear();
for (int i = 1; i <= N; i++)
{
int X, Y1, Y2;
scanf("%d %d %d", &X, &Y1, &Y2);
A1[i] = getAngle(Y1, X);
A2[i] = getAngle(Y2, X);
if (A1[i] < A2[i])
v.push_back( make_pair(A1[i], i) ),
v.push_back( make_pair(A2[i], -i) );
else
v.push_back( make_pair(A1[i], -i) ),
v.push_back( make_pair(A2[i], i) );
}
sort( v.begin(), v.end(), cmp );
in.clear();
int NR = 0;
for (size_t k = 0; k < v.size(); k++)
if (v[k].second > 0)
in.insert( v[k].second );
else
{
if (in.find( -v[k].second ) == in.end())
continue;
NR++; in.clear();
}
printf("%d\n", NR);
return 0;
}