Cod sursa(job #2282840)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 14 noiembrie 2018 16:18:24
Problema Trapez Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 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 val (int v1, int v2) {
    int p = v1 / (N + 1);
    int q = v1 % (N + 1);
    int P = v2 / (N + 1);
    int Q = v2 % (N + 1);
    int semn = ( (pct[q].x - pct[p].x) * (pct[Q].x - pct[P].x) ) > 0 ? 1 : -1;
    return ( 1LL * (pct[q].y - pct[p].y) * (pct[Q].x - pct[P].x) - 1LL * (pct[q].x - pct[p].x) * (pct[Q].y - pct[P].y) ) * semn ;
}
int cmp (int v1, int v2) {
    long long x = val(v1, v2);
    if (x >= 0)
        return 0;
    return 1;
}
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, cmp);
    i = 1;
    while(i<=k)
    {
        if(val(A[i], A[i+1]) == 0 && i < k)
        {
            j=i+1;
            while (val(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;
}