Cod sursa(job #2953530)

Utilizator Victor2006Nicola Victor-Teodor Victor2006 Data 11 decembrie 2022 17:07:57
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <stdio.h>
#include <algorithm>
#define N 120000

struct point { double x, y; };
struct segm { struct point a, b; };

struct point v[N];
struct point start;
int n;

inline bool cmpPanta( struct point a, struct point b, struct point piv ) {
    return (b.y - piv.y) * (a.x - piv.x) < (a.y - piv.y) * (b.x - piv.x);
}

inline double getSquaredLength( struct segm a ) {
    return (a.b.x - a.a.x) * (a.b.x - a.a.x) + (a.b.y - a.a.y) * (a.b.y - a.a.y);
}

inline double getCos( struct point a, struct segm b ) {
    double l1, l2, l3;
    l1 = getSquaredLength({a, b.a});
    l2 = getSquaredLength({b.a, b.b});
    l3 = getSquaredLength({a, b.b});
    if ( l1 > l3 )
        std::swap( l1, l3 );
    return (l1 + l2 - l3) / (2 * sqrt(l1) * sqrt(l2));
}

inline bool cmp( const struct point& a, const struct point& b ) {
    return cmpPanta( a, b, start );
}

int main() {
    FILE *fin, *fout;

    fin = fopen( "infasuratoare.in", "r" );
    fscanf( fin, "%d", &n );
    for ( int i = 0; i < n; i ++ ) {
        fscanf( fin, "%lf%lf", &v[i].x, &v[i].y );
        if ( v[i].x < start.x )
            start = v[i];
        else if ( v[i].x == start.x && v[i].y < start.y )
            start = v[i];

    }
    fclose( fin );

    std::sort( v, v + n, cmp );

    stiva[1] = v[0];
    stiva[2] = v[1];
    stiva[3] = v[2];
    sp = 3;
    for ( int i = 3; i < n; i ++ ) {
        while ( sp > 3 && getCos(v[i], {stiva[sp - 1], stiva[sp - 2]}) > -1 )
            sp --;
    }

    fout = fopen( "infasuratoare.out", "w" );

    fclose( fout );
    return 0;
}