Overview of solution

First, count how many pairs of parallel edges there are. To count them, find the slope between each of \(\frac{N(N-1)}{2}\) possible pairs, and for each slope value \(x\):

• add \(\frac{c_x(c_x-1)}{2}\) to the answer, if there are \(c_x\) pairs with slope \(x\).

Here, a trapezium that is a parallelogram is counted twice each, and a trapezium that is not parallelogram is counted once each. Therefore, we need to subtract the number of parallelograms from the answer. A trapezium is a parallelogram if and only if the two diagonals’ midpoints coincide, so find the midpoint between each of \(\frac{N(N-1)}{2}\) possible pairs, and for each midpoint coordinates \(y\):

• subtract \(\frac{d_y(d_y-1)}{2}\) from the answer, if there are \(d_y\) pairs with midpoint \(y\).

Now every trapezium is counted exactly once, so this algorithm yields a correct answer.

Implementation

If you compute the slope as a floating-point value, precision errors may cause wrong coincidence verdict. Also, slopes like \(1/0\) and \(-1/0\) cause issues. Computing as rational numbers make it easy.

For more details, refer to the following sample code.

Sample code (C++)

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <set>
#include <map>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::pair;
using std::make_pair;
using std::vector;
using std::min;
using std::max;
using std::array;
using std::set;
using std::map;

#include <atcoder/all>
using mint = atcoder::modint998244353;
using atcoder::segtree;

typedef long long int ll;

ll n;
vector<ll> x, y;

ll mygcd (ll a, ll b) {
	if (b == 0) return a;
	return mygcd(b, a % b);
}
ll myabs (ll x) {
	return (x >= 0) ? x : (-x);
}

vector<pair<ll, ll> > slopes;
vector<pair<ll, ll> > centers;
ll countsamepair (const vector<pair<ll, ll> > &vec) {
	ll sum = 0;
	ll idx = 0;
	while (idx < vec.size()) {
		ll j = idx;
		while (j < vec.size() && vec[j] == vec[idx]) j++;

		ll len = j - idx;
		sum += len * (len-1) / 2;

		idx = j;
	}
	return sum;
}
void solve () {
	for (ll i = 0; i < n; i++) {
		for (ll j = i+1; j < n; j++) {
			// slope
			ll px = x[j] - x[i];
			ll py = y[j] - y[i];

			if (px == 0) {
				px = 0;
				py = 1;
			} else if (py == 0) {
				px = 1;
				py = 0;
			} else {
				if (px < 0) {
					px *= -1;
					py *= -1;
				}
				ll g = mygcd(myabs(px), myabs(py));
				px /= g;
				py /= g;
			}

			slopes.push_back({px, py});

			// center
			centers.push_back({x[i]+x[j], y[i]+y[j]});
		}
	}

	ll ans = 0;
	sort(slopes.begin(), slopes.end());
	ans += countsamepair(slopes);
	sort(centers.begin(), centers.end());
	ans -= countsamepair(centers);

	cout << ans << "\n";

	
	return;
}

int main (void) {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n;
	x.resize(n);
	y.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}

	solve();

	return 0;
}