Cod sursa(job #2680940)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 4 decembrie 2020 17:21:18
Problema Patrate 3 Scor 100
Compilator c-64 Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <stdio.h>
#include <ctype.h>
#define MAX_N 1000
FILE *fin;
int x[MAX_N], y[MAX_N];
void sort( int begin, int end ) {
    int aux, b, e, px, py;
    b = begin;
    e = end;
    px = x[(begin + end) / 2];
    py = y[(begin + end) / 2];
    while ( x[b] < px || (x[b] == px && y[b] < py) )
        b++;
    while ( x[e] > px || (x[e] == px && y[e] > py) )
        e--;
    while ( b < e ) {
        aux = x[b];
        x[b] = x[e];
        x[e] = aux;
        aux = y[b];
        y[b] = y[e];
        y[e] = aux;
        do
            b++;
        while ( x[b] < px || (x[b] == px && y[b] < py) );
        do
            e--;
        while ( x[e] > px || (x[e] == px && y[e] > py) );
    }
    if ( begin < e )
        sort( begin, e );
    if ( e + 1 < end )
        sort( e + 1, end );
}
int getCoord() {
    char ch;
    int a, semn;
    while ( isspace( ch = fgetc( fin ) ) );
    semn = 1;
    if ( ch == '-' ) {
        semn = -1;
        ch = fgetc( fin );
    }
    a = 0;
    do
        a = a * 10 + ch - '0';
    while ( (ch = fgetc( fin )) != '.' );
    while ( isdigit( ch = fgetc( fin ) ) )
        a = a * 10 + ch - '0';
    return a * semn;
}
int main() {
    FILE *fout;
    int n, patrate, st, dr, mij, l, c, i, j;
    fin = fopen( "patrate3.in", "r" );
    fscanf( fin, "%d", &n );
    for ( i = 0; i < n; i++ ) {
        x[i] = getCoord();
        y[i] = getCoord();
    }
    fclose( fin );
    sort( 0, n - 1 );
    patrate = 0;
    for ( i = 0; i < n; i++ ) {
        for ( j = i + 1; j < n; j++ ) {
            l = x[i] + y[i] - y[j];
            c = y[i] + x[j] - x[i];
            st = 0;
            dr = n;
            while ( dr - st > 1 ) {
                mij = (st + dr) / 2;
                if ( x[mij] > l || (x[mij] == l && y[mij] > c) )
                    dr = mij;
                else
                    st = mij;
            }
            if ( x[st] == l && y[st] == c ) {
                l = x[j] + y[i] - y[j];
                c = y[j] + x[j] - x[i];
                st = 0;
                dr = n;
                while ( dr - st > 1 ) {
                    mij = (st + dr) / 2;
                    if ( x[mij] > l || (x[mij] == l && y[mij] > c) )
                        dr = mij;
                    else
                        st = mij;
                }
                if ( x[st] == l && y[st] == c )
                    patrate++;
            }
        }
    }
    patrate /= 2;
    fout = fopen( "patrate3.out", "w" );
    fprintf( fout, "%d", patrate );
    fclose( fout );
    return 0;
}