USACO 2020 Gold Problem 3

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define sz(v) (int)v.size()
#define ar array
const int MAXN=2e2+10, INF=1e9+10;

ll r(){
	return ll(rand()&INT_MAX)*INT_MAX+rand();
}

ll el[MAXN];

struct hsh {
	ll a=0;
	int s=0;
	void ad(int c){
		a ^= el[c]; s++;
	}
	void er(int c){
		ad(c); s--;
	}
	ll get(){
		return a;
	}
	int size(){
		return s;
	}
};

int n;
ar<ll, 3> a[MAXN];


int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n; srand(123);
    for (int i = 0; i < n; i++) cin >> a[i][0] >> a[i][1], a[i][2] = i;
    for (int i = 0; i < n; i++) el[i] = r();

	unordered_set<ll> al;

	auto solve = [&](){
		vector<pair<ll, int>> c;
		sort(a, a+n);

		auto get = [&](ll lo, ll hi, ll len){
			sort(c.begin(), c.end());
			int l=lower_bound(c.begin(), c.end(), make_pair(lo, -1))-c.begin(), r=upper_bound(c.begin(), c.end(), make_pair(hi, INF))-c.begin();
			hsh s;
			for (int i = l, j = i; i < r; i++){
				while (j < sz(c) && c[j].first-c[i].first <= len) {
					if (c[j].second != -1) s.ad(c[j].second);
					j++;
				}
				if (s.size() > 1) al.insert(s.get());

				if (c[i].second != -1){
					s.er(c[i].second);
				}
			}
		};
		for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++){
			ll len=a[j][0]-a[i][0], lo=max(a[i][1], a[j][1])-len, hi=min(a[i][1], a[j][1]);
			if (lo > hi) continue;
			assert(len >= 0);
			c.clear();
			for (int k = i; k <= j; k++) c.emplace_back(a[k][1], a[k][2]), c.emplace_back(a[k][1]-len, -1), c.emplace_back(a[k][1]-len+1, -1), c.emplace_back(a[k][1]-len-1, -1);
			get(lo, hi, len);
		}
	};

	for (int rep = 0; rep < 2; rep++){
		solve();
		for (int i = 0; i < n; i++) swap(a[i][0], a[i][1]);
	}
	cout << (n+1+sz(al)) << '\n';
}