Cod sursa(job #1126224)

Utilizator Athena99Anghel Anca Athena99 Data 26 februarie 2014 22:05:23
Problema Rays Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <algorithm>
#include <fstream>

using namespace std;

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

const int nmax= 200000;

struct str{
    int x, y1, y2;
};
str a[nmax+1], b[nmax+1];

bool comp( str x, str y ) {
    return x.x*y.y2>y.x*x.y2;
}

void f( int k, str v[], int &sol ) {
    sort( v+1, v+k+1, comp );
    if ( k>0 ) {
        ++sol;
        int x= v[1].x, y= v[1].y2;
        for ( int i= 2; i<=k; ++i ) {
            if ( x*v[i].y1>y*v[i].x ) {
                ++sol;
                x= v[i].x, y= v[i].y2;
            }
        }
    }
}

int main(  ) {
    int n, k1= 0, k2= 0, sol= 0; 
    fin>>n;
    for ( int i= 1; i<=n; ++i ) {
        str x; 
        fin>>x.x>>x.y1>>x.y2;
        if ( x.y1>x.y2 ) {
            swap(x.y1, x.y2);
        }

        if ( x.x<0 ) {
            x.x= -x.x; b[++k2]= x;
        } else {
            a[++k1]= x;
        }
    }

    f( k1, a, sol ), f( k2, b, sol );
    fout<<sol<<"\n";

    return 0;
}