Cod sursa(job #840680)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 23 decembrie 2012 00:14:04
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#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;
}