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; }