Cod sursa(job #2844006)

Utilizator Victor2006Nicola Victor-Teodor Victor2006 Data 3 februarie 2022 15:58:48
Problema Trapez Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <stdio.h>
#include <algorithm>
#define N 1000
#define LMAX 20
#define AINF 2000000001
#define EPSILON 0.0001

struct pct {
    int x;
    int y;
};

double a[(N - 1) * N / 2 + 1];
pct v[N];
int n;

inline bool isEqual( double a, double b ) {
    double x = a - b;
    if ( x < 0 )
        x = -x;
    return (x < EPSILON);
}

int firstVal( double v[], int n, double val ) {
    int poz = 0, pas = 1 << LMAX;
    while ( pas ) {
        if ( poz + pas < n && v[poz + pas] < val )
            poz += pas;
        pas /= 2;
    }
    if ( poz == 0 && isEqual( v[poz], val ) )
        return poz;
    if ( isEqual( v[poz + 1], val ) )
        return poz + 1;
    // nu exista val in vector
    return -1;
}

int lastVal( double v[], int n, double val ) {
    int poz = 0, pas = 1 << LMAX;
    while ( pas ) {
        if ( poz + pas < n && v[poz + pas] <= val )
            poz += pas;
        pas /= 2;
    }
    if ( isEqual( v[poz], val ) )
        return poz;
    // nu exista val in vector
    return -1;
}

inline double getPanta( pct a, pct b ) {
    if ( a.x == b.x )
        return AINF;
    return (double)(b.y - a.y) / (b.x - a.x);
}

void precalcPanta() {
    int poz = 0;
    for ( int i = 0; i < n; i ++ )
        for ( int j = i + 1; j < n; j ++ )
            a[poz ++] = getPanta( v[i], v[j] );
    std::sort( a, a + poz );
    a[poz] = AINF + 5;
}

bool cmp( const pct& a, const pct& b ) {
    if ( a.x < b.x || (a.x == b.x && a.y < b.y) )
        return true;
    return false;
}

int main() {
    FILE *fin, *fout;
    int cnt;
    double p;

    fin = fopen( "trapez.in", "r" );
    fscanf( fin, "%d", &n );
    for ( int i = 0; i < n; i ++ )
        fscanf( fin, "%d%d", &v[i].x, &v[i].y );
    fclose( fin );

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

    cnt = 0;
    for ( int i = 0; i < n; i ++ ) {
        for ( int j = i + 1; j < n; j ++ ) {
            p = getPanta( v[i], v[j] );
            cnt += lastVal( a, (n - 1) * n / 2, p ) -
                   firstVal( a, (n - 1) * n / 2, p );
        }
    }

    fout = fopen( "trapez.out", "w" );
    fprintf( fout, "%d\n", cnt / 2 );
    fclose( fout );
    return 0;
}