Cod sursa(job #2646348)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 31 august 2020 20:48:19
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define NMAX 1005
#define ll long long

int n;
pii p[NMAX];

vector<long long> v;

int main()
{
    freopen("trapez.in","r",stdin);
    freopen("trapez.out","w",stdout);

    cin >> n;
    for (int i=1;i<=n;i++){
        cin >> p[i].first >> p[i].second;
    }

    for (int i=1;i<=n;i++){
        for (int j=i+1;j<=n;j++){
            int a = p[j].second - p[i].second;
            int b = p[j].first - p[i].first;
            int d = __gcd(a, b);
            a /= d;
            b /= d;
            v.push_back(a * 2000000001LL + b);
        }
    }

    sort(v.begin(),v.end());

    ll lst = -1, cnt = 0;
    int ans = 0;
    for (auto it : v){
        if (it != lst){
            ans += (cnt * (cnt-1) / 2);
            cnt = 1;
            lst = it;
        }
        else{
            cnt++;
        }
    }
    ans += (cnt * (cnt - 1) / 2);

    cout << ans << '\n';

    return 0;
}