Cod sursa(job #1515516)

Utilizator felixiPuscasu Felix felixi Data 1 noiembrie 2015 18:33:17
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <algorithm>
#include <fstream>

using namespace std;

ifstream in("rays.in");
ofstream out("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;
    in>>n;
    for ( i64 i= 1; i<=n; ++i ) {
        str x;
        in>>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 );
    out<<sol<<"\n";

    return 0;
}