Cod sursa(job #1840682)

Utilizator giotoPopescu Ioan gioto Data 4 ianuarie 2017 18:44:00
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int n, x[1001], y[1001];
long long l[1000001];
int pos[1000001];
double p[1000001];
long long Sol;
inline bool cmp(int x, int y){
    if(p[x] != p[y]) return p[x] < p[y];
    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){
            if(x[i] != x[j]) p[++NR] = (double)(y[j] - y[i]) / (double)(x[j] - x[i]);
            else p[++NR] = 1000000000;
            l[NR] = (long long)(x[i] - x[j]) * (long long)(x[i] - x[j]) + (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(p[pos[j]] == p[pos[j + 1]]){
            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;
}