题解【P7153 [USACO20DEC] Square Pasture G 】

__gcd · 2021-01-29 17:43:14 · 题解

标签：平面坐标+双指针

思考+调试总共耗时7h，写篇题解纪念一下。

基本思路

• 第一种情况，空集或者只包含一个点。

显然，答案为 n+1。

• 第二种情况，包含两个及以上的点。

枚举正方形最左和最右的两个点 i,j(i<j)，满足 |x_i-x_j|\geq |y_i-y_j|，则正方形的边长 side=|x_i-x_j|。对于 |x_i-x_j|\leq |y_i-y_j| 的情况，可以通过交换每个点的 x,y 坐标再通过相同的方式得到答案，这里就不再讨论。

对所有坐标以 x 坐标为第一关键字，y 坐标为第二关键字排序。排序之后，正方形中所有点的下标必定在 [i,j] 之间，x 坐标必定在 [x_i,x_j] 之间。

考虑 y 坐标，不妨将下标在 [i,j] 之间的点的 y 坐标排序后放在一个长度为 j-i+1 的数组 v 中。这样，正方形中的点的 y 坐标一定属于数组 v 的一个连续区间。问题转变为了求出这个区间的两端点 l,r 有多少种组合方式。因为 v 数组有序，所以可以使用双指针来解决这个问题。

双指针的具体实现

这里的双指针类似于滑动一个长度为 side 的窗口。

首先确定 v_l 和 v_r 的范围。因为正方形必须包含 i,j 两点，所以设 mini=\max(y_i,y_j)-side，maxi=\min(y_i,y_j)，那么正方形的下边界 lower\in[mini,maxi]，上边界 upper\in[mini+side,maxi+side]。

注：上边界和下边界并不代表 v_l 和 v_r。

接下来讨论什么样的 [l,r] 是合法的。需要满足以下两个条件。

• 正方形必须能同时包含 v_l 和 v_r 两个坐标，即 v_l\leq v_r-side。

• 正方形不能包括 v_{r+1}，同样不能包括 v_{l-1}。

  这个条件的讨论有一些复杂。不妨固定右端点 r，去寻找可行的左端点。

  包含 v_r 且不包含 v_{r+1}，正方形的上边界需要满足 upper\in[v_r,v_{r+1}-1]，对应到下边界就是 lower\in[v_r-side,v_{r+1}-1-side]。要使 l 合法，则需 \exists lower[v_r-side,v_{r+1}-1-side]，使得 lower>v_{l-1}。那么只要使 lower 的最大值 v_{r+1}-1-side>v_{l-1} 即可。

  所以只要满足 v_{r+1}-1-side>v_{l} 便可将指针 l 向右移动一位，即 l\gets l+1。

最后还有 |x_i-x_j|\geq |y_i-y_j| 和 |x_i-x_j|\leq |y_i-y_j| 出现重复的问题。如果在统计的时候出现 v_r-v_l=side 的情况，那么当 l,r 对应的下标成为下一轮枚举的 i,j 时，这个正方形中包含的子集会被再统计一次，减去即可。

这道题还有很多的细节，详情请见代码。（当然你问我为什么代码显示不全，是因为代码太宽了233，只需要复制到编辑器里就可以看了）

#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
inline int read() {
    int x = 0; bool op = false;
    char c = getchar();
    while(!isdigit(c))op |= (c == '-'), c = getchar();
    while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return op ? -x : x;
}
const int N = 210;
int n, ans, res;
struct Node {
    int x, y;
    bool operator < (const Node &tmp) const {
        if(x ^ tmp.x)return x < tmp.x;
        else return y < tmp.y;
    }
    Node(int x = 0, int y = 0):x(x), y(y){}
}a[N];
set<int> s;
void solve() {
    sort(a + 1, a + 1 + n);
    for(int i = 1; i < n; i++) {
        s.clear(); s.insert(a[i].y);
        for(int j = i + 1; j <= n; j++) {
            s.insert(a[j].y);
            vector<int> vec(s.begin(), s.end()); //从题解里面学到的奇怪操作，相当于把s中的元素复制到了vec里 
            int side = a[j].x - a[i].x;
            int mini = max(a[i].y, a[j].y) - side, maxi = min(a[i].y, a[j].y);
            if(mini > maxi)continue; //如果下界在上界之上，直接跳过 
            int len = vec.size(), l = 0, r = -1;
            while(r + 1 < len && vec[r + 1] < mini + side)r++; 
            //找到最大的r，使得vec[r]<mini+side
            //之所以要这么找，是因为可能存在上界在[mini+side,maxi+side]之中但是vec[r]不在这个区间之中的情况
            //那么包含它且不包含vec[r+1]的条件也有所转变，即上界在[mini+side,vec[r+1]-1]之间。 
            while(l < len && vec[l] < mini)l++; //找到最小的l，使vec[l]>=mini 
            for(; r < len && (r < 0 || vec[r] <= maxi + side); r++) {//我比较喜欢这种双指针的写法，即确定r枚举l 
                if(r < 0)continue; //r<0直接跳过 
                int tl = max(vec[r] - side, mini);
                int tr = min((r + 1 < len) ? vec[r + 1] - side : maxi + 1, maxi + 1) - 1;
                //如果r+1不存在，那么把上界设为maxi+1（因为后面有一个-1所以不能设为maxi）
                //此时正方形下边界的范围为[tl,tr] 
                while(l < len && vec[l] < tl)l++;//首先提出vec[l]在下边界以下的情况 
                if((vec[r] < mini + side && vec[r + 1] > mini + side) || vec[r] >= mini + side)ans++;
                //细节：此时r增加了1，不管l能不能移动，它都是一种新的情况，需要统计答案
                //当然其中也有不合法的答案，比如说vec[r]在下边界一下，但是上边界根本不可能移动到mini+side以上
                //这种情况就是ver[r+1]正好等于mini+side
                if(vec[r] - vec[l] == side)res++; //去重 
                while(l + 1 < len && vec[l] < tr) {ans++; l++; if(vec[r] - vec[l] == side)res++;}//统计答案+去重 
            }
        }
    }
    return ;
}
int main() {
    n = read(); ans = n + 1; 
    for(int i = 1; i <= n; i++) {int x = read(), y = read(); a[i] = Node(x, y);}
    solve(); 
    for(int i = 1; i <= n; i++)swap(a[i].x, a[i].y);
    solve();
    printf("%d", ans - res / 2);
    return 0;
}