Cod sursa(job #2844200)

Utilizator Victor2006Nicola Victor-Teodor Victor2006 Data 3 februarie 2022 22:20:23
Problema Trapez Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
// TLE de la double
#include <stdio.h>
#include <algorithm>
#define N 1000
#define LMAX 20
#define PUT10 1000000LL
#define AINF (2000000000 * PUT10 + 1)
#define EPSILON 10

struct pct {
    int x;
    int y;
};

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

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

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

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

inline long long getPanta( pct a, pct b ) {
    if ( a.x == b.x )
        return AINF;
    return (b.y - a.y) * PUT10 / (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;
    long long 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 );

    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( (n - 1) * n / 2, p ) -
                   firstVal( (n - 1) * n / 2, p );
        }
    }

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