Cod sursa(job #2789638)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 27 octombrie 2021 19:07:02
Problema Trapez Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <unordered_map>
#include <chrono>

FILE *fin, *fout;

const int NMAX = 1e3;
const int INF = 1e9;

const int P = 2e9;
const int p = 638883;
const int MOD = 660073;

int N, ans;
std :: pair <int, int> v[NMAX + 1];
int fr[MOD];

int panta(std :: pair <int, int> a, std :: pair <int, int> b) {
    int gcd = std :: __gcd((a.second - b.second), (a.first - b.first));
    return (((long long)(a.second - b.second) / gcd * p) % MOD + (long long)(a.first - b.first) / gcd + MOD) % MOD;
}

int main() {
    fin = fopen("trapez.in", "r");
    fout = fopen("trapez.out", "w");

    fscanf(fin, "%d", &N);

    for(int i = 1; i <= N; i++) {
        int x, y;
        fscanf(fin, "%d %d", &x, &y);
        v[i] = {x, y};
    }

    for(int i = 1; i <= N; i++) {
        for(int j = i + 1; j <= N; j++) {
//            printf("%d %d %d\n", i, j, panta(v[i], v[j]));
            fr[panta(v[i], v[j])]++;
        }
    }

    for(int i = 0; i < MOD; i++) {
        if(fr[i] < 2) {
            continue;
        }
//        printf("%d %d %d\n", i, fr[i], fr[i] * (fr[i] - 1) / 2);
        ans += fr[i] * (fr[i] - 1) / 2;
    }

    fprintf(fout, "%d", ans);
    return 0;
}