Pagini recente » Monitorul de evaluare | Cod sursa (job #1245179) | Cod sursa (job #121285) | Cod sursa (job #1729469) | Cod sursa (job #840680)
Cod sursa(job #840680)
#include <fstream>
using namespace std;
ifstream f ( "rays.in" );
#include <algorithm>
ofstream g ( "rays.out" );
#define eps 0.000000001
#define LE 206000
int i;
pair<double, double> A[2][LE];
double min_left;
int result, n;
int Right;
int rr, le;
pair<double, double> panta ( int LINE, int UP, int DOWN )
{
return make_pair ( ( double ) DOWN / LINE , ( double ) UP / LINE );
};
double Mod ( double value )
{
return value > 0 ? value : -value;
}
double minr(double X,double Y)
{
return X<Y?X:Y;
}
inline bool comp ( pair<double, double> AA, pair<double, double> BB )
{
if ( Mod ( AA.first - BB.first ) > eps )
return AA.first < BB.first;
return AA.second < BB.second;
}
void solve ( int lin, int N )
{
for ( i = 1; i <= N; ++i )
{
min_left = A[lin][i].second;
Right = i;
++result;
while ( Right + 1 <= N && A[lin][Right+1].first <= min_left )
{
++Right;
min_left=minr(A[lin][Right].second,min_left);
}
i = Right;
}
}
int main()
{
f >> n;
for ( i = 1; i <= n; ++i )
{
int line, upp, down;
f >> line >> upp >> down;
if ( upp < down )
swap ( upp, down );
if ( line > 0 )
A[0][++rr] = panta ( line, upp, down );
else
A[1][++le] = panta ( -line, upp, down );
}
sort ( A[0] + 1, A[0] + rr + 1, comp );
sort ( A[1] + 1, A[1] + le + 1, comp );
// solve ( 0, rr );
// solve ( 1, le );
g << result << '\n';
f.close();
g.close();
return 0;
}