Cod sursa(job #1840699)

Utilizator giotoPopescu Ioan gioto Data 4 ianuarie 2017 19:03:39
Problema Trapez Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int n, x[1001], y[1001];
long long l[1000001];
int pos[1000001];
int p1[1000001], p2[1000001];
long long Sol;
inline bool cmp(int x, int y){
    if(1LL * p1[x] * p2[y] != p1[y] * p2[x]) return 1LL * p1[x] * p2[y] < 1LL * p1[y] * p2[x];
    return l[x] < l[y];
}
int main()
{
    freopen("trapez.in", "r", stdin);
    freopen("trapez.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n ; ++i)
        scanf("%d%d", &x[i], &y[i]);
    int NR = 0;
    for(int i = 1; i <= n ; ++i){
        for(int j = i + 1; j <= n ; ++j){
            p1[++NR] = y[j] - y[i];
            p2[NR] = x[j] - x[i];
            int a = p1[NR], b = p2[NR], r;
            while(b != 0){
                r = a % b;
                a = b; b = r;
            }
            p1[NR] /= a; p2[NR] /= a;
            l[NR] = (long long)(x[i] - x[j]) * (long long)(x[i] - x[j]) + (long long)(y[i] - y[j]) * (y[i] - y[j]);
            pos[NR] = NR;
        }
    }
    sort(pos + 1, pos + NR + 1, cmp);
    int i = 1;
    while(i <= NR){
        int j = i, k = 0, nr = 0;
        while(p1[pos[j]] * p2[pos[j + 1]] == p1[pos[j + 1]] * p2[pos[j]] && j < NR){
            if(l[pos[j]] == l[pos[j + 1]]) ++nr;
            else Sol = Sol + (long long)nr * (nr + 1) / 2, nr = 0;
            ++k; ++j;
        }
        i = j + 1;
        Sol = Sol + (long long)nr * (nr + 1) / 2;
        Sol = Sol + (long long)k * (k + 1) / 2;
    }
    printf("%lld", Sol);
    return 0;
}