Cod sursa(job #1126233)

Utilizator Athena99Anghel Anca Athena99 Data 26 februarie 2014 22:07:47
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <algorithm>
#include <fstream>

using namespace std;

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

typedef long long i64;

const i64 nmax= 200000;

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

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

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

int main(  ) {
    i64 n, k1= 0, k2= 0, sol= 0; 
    fin>>n;
    for ( i64 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;
}