USACO 2020 December Contest, Gold Problem 3. Square Pasture

USACO 2020 December Contest, Gold Problem 3. Square Pasture

Farmer John's largest pasture can be regarded as a large 2D grid of square "cells" (picture a huge chess board). Currently, there are NN cows occupying some of these cells (1≤N≤2001≤N≤200).

Farmer John wants to build a fence that will enclose a square region of cells; the square must be oriented so its sides are parallel with the xx and yy axes, and it could be as small as a single cell. Please help him count the number of distinct subsets of cows that he can enclose in such a region. Note that the empty subset should be counted as one of these.

 

Note that although the coordinates of cells with cows are nonnegative, the square fenced area might possibly extend into cells with negative coordinates.

 

 

SAMPLE INPUT:

4
0 2
2 3
3 1
1 0

SAMPLE OUTPUT:

14

In this example, there are 2424 subsets in total. FJ cannot create a fence enclosing only cows 1 and 3, or only cows 2 and 4, so the answer is 24−2=16−2=1424−2=16−2=14.

 

SAMPLE INPUT:

16
17 4
16 13
0 15
1 19
7 11
3 17
6 16
18 9
15 6
11 7
10 8
2 1
12 0
5 18
14 5
13 2

SAMPLE OUTPUT:

420

 

 

Problem credits: Benjamin Qi

 USACO 2020 December Contest, Gold Problem 3. Square Pasture 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

For a set of greater than one cow that can be covered by a square, let the bounding rectangle of the set be the rectangle of the minimum size with sides parallel to the coordinates axes that contains all cows in the set.

It suffices to deal with the case where the width of the bounding rectangle is greater or equal to its height. (We can handle the other case by swapping all xx and yy coordinates and rerunning the solution, while making sure not to overcount bounding rectangles with equal width as height.)

Fix the leftmost and rightmost cows a=(xa,ya)a=(xa,ya) and b=(xb,yb)b=(xb,yb) (xa<xbxa<xb) in the set. Then we must be able to cover all cows in the set (and none outside of it) with a square that contains aa on its left side and bb on its right side. The square will include all cows (xt,yt)(xt,yt) such that xt∈[xa,xb]xt∈[xa,xb] and yt∈[y,y+xb−xa]yt∈[y,y+xb−xa] for some y∈[lo,hi]y∈[lo,hi], where lo=max(ya,yb)−(xb−xa)lo=max(ya,yb)−(xb−xa) and hi=min(ya,yb)hi=min(ya,yb). Note that if lo>hilo>hi, this would contradict the assumption that the height of the bounding rectangle is less than or equal to the width.

Given the yy-coordinates of all cows (xc,yc)(xc,yc) satisfying xa<xc<xbxa<xc<xb, we can compute the number of such squares in O(NlogN)O(Nlog⁡N) by sorting the yy-coordinates and using two pointers. Start with the bottom side of the square at y=loy=lo and increase yy until a new cow enters the set through the top side or leaves the set through the bottom side (or both at once).

This gives a solution that runs in O(N3logN)O(N3log⁡N) or O(N3)O(N3) time.

 

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

using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) int((x).size())

int N,ans,eq;
vector<pi> cows;
 
void solve() {
	sort(begin(cows),end(cows));
	for (int a = 0; a < N; ++a) { // leftmost cow a
		set<int> sorted_y; // set of y-coordinates for cows a+1..b-1
		for (int b = a+1; b < N; ++b) { // rightmost cow b
			if (a < b-1) sorted_y.insert(cows[b-1].s);
			int len = cows[b].f-cows[a].f; // side length of square
			int lo = max(cows[a].s,cows[b].s)-len, hi = min(cows[a].s,cows[b].s); 
			if (lo > hi) continue;

			// initialize the square as [cows[a].f,cows[b].f] x [lo,lo+len]
			vector<int> y(begin(sorted_y),end(sorted_y)); 
			int l = 0, r = -1;
			// find cow of lowest y-coordinate that square currently contains
			while (l < sz(y) && lo >= y[l]+1) l ++; 
			// find cow of highest y-coordinate that square currently contains
			while (r+1 < sz(y) && lo >= y[r+1]-len) r ++; 
			// initial square currently includes cows [l,r]

			while (1) { // repeatedly increase y
				++ ans;
				int yl = min(cows[a].s,cows[b].s), yr = max(cows[a].s,cows[b].s);
				if (l <= r) yl = min(yl,y[l]), yr = max(yr,y[r]);
				assert(yr-yl <= len); 
				eq += yr-yl == len; // width is equal to height
				// current bounding rectangle is [cows[a].f,cows[b].f] x [yl,yr]
				int leave_bottom = (l < sz(y) ? y[l]+1 : INT_MAX);  // set will no longer include cow l
				int enter_top    = (r+1 < sz(y) ? y[r+1]-len : INT_MAX); // set will include cow r+1
				int change_y = min(leave_bottom ,enter_top); // find min y such that set changes
				if (change_y > hi) break;
				l += leave_bottom == change_y;
				r += enter_top == change_y;
			}
		}
	}
}
 
int main() {
	cin >> N; cows.resize(N); 
	for (pi& cow: cows) cin >> cow.f >> cow.s;
	ans = N+1;

	solve();
	for(pi& cow: cows) swap(cow.f,cow.s);
	solve();

	assert(eq%2 == 0); // bounding rectangles with equal width as height counted twice
	cout << ans-eq/2;
}

Note that the answer to this problem would be different if the cows were treated as points rather than squares. For example, if the input was

 

4
0 2
2 3
3 0
4 1

then we cannot create a square that encloses only the cows occupying cells (2,3)(2,3) and (3,0)(3,0).

[/hide]