Cod sursa(job #2282872)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 14 noiembrie 2018 17:34:37
Problema Trapez Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("trapez.in");
ofstream g("trapez.out");
struct points
{
    int x, y;
}pct[1001];
int N, i, j, k, A[500003];
long long sum;
long long values (int v1, int v2) {
    int p = v1 / (N + 1);
    int q = v1 % (N + 1);
    int P = v2 / (N + 1);
    int Q = v2 % (N + 1);
    long long dx1 = (pct[q].x - pct[p].x);
    long long dy1 = (pct[q].y - pct[p].y);
    long long dx2 = (pct[Q].x - pct[P].x);
    long long dy2 = (pct[Q].y - pct[P].y);
    int semn = (  dx1 * dx2 >= 0 ) ? 1 : -1;
    return (dy1 * dx2 - dx1 * dy2) * semn ;
}
int cmpv (int v1, int v2) {
    long long x = values(v1, v2); ;
    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++)
            A[++k] = (N + 1) * i + j;
    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;
}