Cod sursa(job #1754335)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 7 septembrie 2016 22:17:40
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in ( "rays.in"  );
ofstream out( "rays.out" );

vector< tuple<int, int, int> > l1, l2;

bool comp( tuple<int, int, int> a, tuple<int, int, int> b ) {
    return get<0>(a) * 1LL * get<2>(b) > get<0>(b) * 1LL * get<2>(a);
}

int solve( vector< tuple<int, int, int> > &l ) {
    int ans = 1; tuple<int, int> p;

    if( l.size() == 0 )
        return 0;

    sort( l.begin(), l.end(), comp );
    p = make_tuple( get<0>(l[0]), get<2>(l[0]) );

    for( int i = 1; i < l.size(); i ++ ) {
        if( get<0>(p) * 1LL * get<1>(l[i]) > get<1>(p) * 1LL * get<0>(l[i]) ) {
            ans ++;
            p = make_tuple( get<0>(l[0]), get<2>(l[0]) );
        }
    }

    return ans;
}

int main( void ) {

    int n; in >> n;
    for( int i = 1; i <= n; i ++ ) {
        int x, y1, y2; in >> x >> y1 >> y2;

        if( y1 > y2 )
            swap( y1, y2 );

        if( x < 0 )
            l1.push_back( make_tuple( -x, y1, y2 ) );
        else
            l2.push_back( make_tuple( +x, y1, y2 ) );
    }

    out << solve( l1 ) + solve( l2 ) << endl;
    return 0;
}