Cod sursa(job #2282876)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 14 noiembrie 2018 17:43:29
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("trapez.in");
ofstream g("trapez.out");
struct points
{
    int x, y;
}pct[1001];
struct segment {
    points P, Q;
    int dx, dy;
}A[500003];
int N, i, j, k;
long long sum;
long long values (segment V, segment W) {
    int semn = ( 1LL * V.dx * W.dx >= 0 ) ? 1 : -1;
    return (1LL * V.dy * W.dx - 1LL * V.dx * W.dy) * semn ;
}
int cmpv (segment V, segment W) {
    long long x = values(V, W);
    return x >= 0;
}
int main()
{
    f >> N;
    for (i = 1; i <= N; i++)
        f >> pct[i].x >> pct[i].y;
    k = 0;
    for (i = 1; i <= N ; i++)
        for (j = i + 1; j <= N; j++) {
            ++k;
            A[k].P = pct[i];
            A[k].Q = pct[j];
            A[k].dx = pct[j].x - pct[i].x;
            A[k].dy = pct[j].y - pct[i].y;
        }

    sort(A + 1, A + k + 1, cmpv);
    i = 1;
    while(i <= k) {
        if (values(A[i], A[i+1]) == 0 && i < k) {
            j = i + 1;
            while (values(A[j], A[j + 1]) == 0 && j < k)
                ++j;
            sum = sum + (j - i + 1) * 1LL * (j - i) / 2;
            i = j;
        }
        i++;
    }
    g << sum;
    return 0;
}