双队列或双指针解决Square Pasture(Glod)

此题是本次比赛最难一题了，解题细节比较多，非常考验编程能力。使用双指针vector，模拟正方形运动。不断移动两个vector的指针直到end()指针、这是官方题解思路。但我使用了个不同的数据结构queue替代vector，指针永远在top(),实现更就简单并且性能更快，性能有2-10倍的提升。

详细如下：

题目来源

USACO 2020 December Contest, Gold Problem 3. Square Pasture

题意

题意和银组这题类似Rectangular Pasture，但是这题由长方形改成了正方形。坐标数量也缩小了($1 \le N \le 200$)。银组的解法参考《乘法原理解决Rectangular Pasture(Silver)》

初步想法

通过观察图形，初步思路：

不能离散化，因为离散化后坐标先对位置虽然不变，但矩形形状会变化，可能会变成正方形，导致错误结果。
设定任意两点，例如$a$和$b$，一左一右，$a.x < b.y$。
以$a$和$b$为对角形成一个最小矩形。
最小矩形沿着上、下方向拓展可形成正方形。
移动正方形，看看能包住多少种牛？

如下图，滑动正方形，可以包住牛的情况有5种：

第1种情况

往上移动，发现还是和第1种情况一样，算1种情况

继续往上移动，第2种情况：

继续往上移动，第3种情况：

继续往上移动，第4种情况：

继续往上移动，第5种情况：

不能再移动了，这个正方形的移动范围如下：简单说就是从lo这个位置到a点这个位置。lo这个位置很好计算。

进一步思路

问题1：如果$a$和$b$这两点形成的矩形是竖的情况，矩形拓展+移动是左右了，而不是上下了，如下：
问题2：如果$a$和$b$这两点形成的矩形正好是正方形，就无需拓展+移动了，仅这一种情况。
问题3：通过模拟正方形移动，每次移动累加答案，但如何模拟移动正方形？

问题1，分两次计算

第1次计算，$a$和$b$形成是横向矩形（包括正方形），忽略竖向的矩形。第2次旋转90度（通过交换坐标x,y），再跑一次累加计算。

问题2

以上办法可能导致正方形的数量重复计算，重复情况放到问题4。
可在问题1分两次计算时候累加出重复情况的数量，再最后答案扣减重复部分。

问题3，模拟正方形滑动，是比较复杂部分：

由最下往上滑动（反过来也可以）
在$a+1…b-1$之间的所有的牛，把其Y坐标，放到到set里面，使用set自动排序。这些牛，正方形有可能能包含，也有可能不能包含。
把矩形下方的牛放入队列1，上方的牛放入队列2。
分别找队列1、队列2在队列top牛，比较距离，正方形往最近的牛移动，几种情况：
1. 下面牛消失，上面牛无进入，出队。上、下边界不可能有牛，不累加重复。
2. 下面牛消失同时上面牛进入，出队。上、下边界可能有牛，累加重复。
3. 下面牛无消失，上面牛进入，出队。上、下边界可能有牛，累加重复。
两个队列都是空队列，表示不能移动了，结束。
每次移动都累计答案。
另外队列也可以使用vector代替，队列的出队，使用vector的指针后移，直到end()指针。
两个vector都到达end()指针表示不能移动了，结束。
队列版本比较容易实现，速度比较快。
为了方便阅读代码，我做了分析图如下，请对着后面的代码查阅。

问题4：重复情况，经过观察，关键是仅判断正方形上、下边是否有牛：

$a$和$b$本身形成正方形，此时$a$和$b$是正方形的对角线，上、下、左、右边有牛，旋转之后上、下、左、右边有牛还是同样的牛，正方形含牛的情况一样。如下黄色区域：
$a$和$b$本身形不是正方形，但拓展的正方形上下两边同时都有牛(包含$a$和$b$)，旋转之后正方形包含牛的情况一样。如下黄色区域：

队列(queue)版本（双队列）

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192


#ifndef LOCAL_DEBUG
#define NDEBUG //ban assert when submit to online judge
#endif

#ifdef LOCAL_DEBUG
#include <chrono>
#endif

#include <bits/stdc++.h>

#define FastIO                        \
    ios_base::sync_with_stdio(false); \
    std::cin.tie(nullptr);            \
    std::cout.tie(nullptr)

using namespace std;

using ill = long long;
const int INF = INT_MAX / 2;

#define x first
#define y second

class solution
{
  private:
    vector<pair<int, int>> cows;
    int n;
    int repeat;
    int sum()
    {
        sort(cows.begin(), cows.end());
        int curAns = 0;
        for (int a = 0; a <= n - 1; ++a)
        {
            set<int> ySet; //在a+1...b-1之间的牛Y坐标，使用set自动排序
            for (int b = a + 1; b <= n - 1; ++b)
            {
                if (b - 1 != a)                 //相邻的牛不放进去
                    ySet.insert(cows[b - 1].y); //放入b的上一个牛

                int squareLen = cows[b].x - cows[a].x;  //正方形的长度;
                int top = max(cows[a].y, cows[b].y);    //最小矩形顶部
                int bottom = min(cows[a].y, cows[b].y); //最小矩形底部

                int lo = top - squareLen;               //正方形移动区域（最底）
                int hi = bottom + squareLen;            //正方形移动区域（最高）
                
                if (lo > bottom) //竖的长方形
                {
                    continue;
                }
                else if (lo == bottom) //a:b正好组成正方形
                {
                    ++repeat;
                    ++curAns;
                    //cerr << a << ":" << b << ":" << curAns << "\n";
                    continue;
                }

                if (ySet.empty()) //a,b之间Y坐标上没有牛
                {
                    ++curAns;
                    //cerr << a << ":" << b << ":" << curAns << "\n";
                    continue;
                }

                //准备正方形需要的数据

                queue<int> yLowQ;   //在正方形内，低于bottom的牛,在lo和bottom之间的牛,存放y坐标
                queue<int> yHightQ; //在正方形内，高于top的牛，在top和hi之间，存放y坐标

                for (auto it = ySet.begin(); it != ySet.end(); ++it)
                {
                    int currY = (*it);
                    if (currY >= lo && currY < bottom)
                        yLowQ.push(currY);

                    if (currY > top && currY <= hi)
                        yHightQ.push(currY);
                }

                if (yLowQ.empty() && yHightQ.empty()) //在正方形移动范围内没有牛
                {
                    ++curAns;
                    cerr << a << ":" << b << ":" << curAns << "\n";
                    continue;
                }

                //向上移动正方形，使得每次下边界有牛消失或上边界有牛进入，或者两个同时有
                //在ySetLow和ySetHight跳跃

                //判断正方形上下边是否有牛，有就计算重复数，旋转90度会重复
                auto checkRepeat=[&]()
                {
                    if (!yLowQ.empty() && yLowQ.front() - lo == 0) //最底低边是否有牛
                        ++repeat;
                    else if (lo == bottom)                                  //最底低已经达到bottom
                        ++repeat;                    
                };
                
                checkRepeat();

                while (true)
                {
                    ++curAns;

                    int downDist = yLowQ.empty() ? INF : yLowQ.front() - lo;    //底部指针离最近的牛的距离
                    int upDist = yHightQ.empty() ? INF : yHightQ.front() - top; //顶部部指针离最近的牛的距离

                    if (downDist == INF && upDist == INF)
                    {
                        break;
                    }
                    else
                    {
                        //移动到最近的牛，按上下距离最小值
                        lo +=min(downDist + 1,upDist);

                        if (downDist + 1 < upDist)  //下面牛消失，上面牛无进入
                        {
                            yLowQ.pop();
                        }
                        else if (downDist + 1 == upDist)    //下面牛消失同时上面牛进入
                        {
                            yLowQ.pop();
                            yHightQ.pop();

                            //判断正方形上下边是否有牛，旋转90度会重复
                            checkRepeat();
                        }
                        else                                //下面牛无消失，上面牛进入
                        {
                            yHightQ.pop();

                            //判断正方形上下边是否有牛，旋转90度会重复
                            checkRepeat();
                        }
                    }
                    top = lo + squareLen;   //同时移动top
                }

                //cerr << a << ":" << b << ":" << curAns << "\n";
            }
        }
        return curAns;
    }

  public:
    void solve()
    {
        cin >> n;

        int ans = n + 1;
        cows = vector<pair<int, int>>(n);
        for(auto & c:cows)
            cin >> c.x >> c.y;
        ans += sum();

        //转90度
        for(auto & c:cows)
            swap(c.x,c.y);
        ans += sum();
        
        assert(repeat % 2 == 0);
        cout << ans - repeat / 2 << "\n";
        
    }
};

signed main()
{
    FastIO;

#ifdef LOCAL_DEBUG
    freopen("SquarePasture.in", "r", stdin);
    //freopen("SquarePasture.out", "w", stdout);
    auto startTime = chrono::high_resolution_clock::now();
#endif

    solution sln1;
    sln1.solve();
    cout.flush();

#ifdef LOCAL_DEBUG
    cerr << "Execution time: "
         << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - startTime).count()
         << " ms\n";
#endif

    return 0;
}

vector版本（双指针）

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193


#ifndef LOCAL_DEBUG
#define NDEBUG //ban assert when submit to online judge
#endif

#ifdef LOCAL_DEBUG
#include <chrono>
#endif

#include <bits/stdc++.h>

#define FastIO                        \
    ios_base::sync_with_stdio(false); \
    std::cin.tie(nullptr);            \
    std::cout.tie(nullptr)

using namespace std;

using ill = long long;
const int INF = INT_MAX / 2;

#define x first
#define y second

class solution
{
  private:
    vector<pair<int, int>> cows;
    int n;
    int repeat;
    int sum()
    {
        sort(cows.begin(), cows.end());
        int curAns = 0;
        for (int a = 0; a <= n - 1; ++a)
        {
            set<int> ySet; //在a+1...b-1之间的牛Y坐标，使用set自动排序
            for (int b = a + 1; b <= n - 1; ++b)
            {
                if (b - 1 != a)                 //相邻的牛不放进去
                    ySet.insert(cows[b - 1].y); //放入b的上一个牛

                int squareLen = cows[b].x - cows[a].x;  //正方形的长度;
                int top = max(cows[a].y, cows[b].y);    //最小矩形顶部
                int bottom = min(cows[a].y, cows[b].y); //最小矩形底部

                int lo = top - squareLen;               //正方形移动区域（最底）
                int hi = bottom + squareLen;            //正方形移动区域（最高）
                
                if (lo > bottom) //竖的长方形
                {
                    continue;
                }
                else if (lo == bottom) //a:b正好组成正方形
                {
                    ++repeat;
                    ++curAns;
                    cerr << a << ":" << b << ":" << curAns << "\n";
                    continue;
                }

                if (ySet.empty()) //a,b之间Y坐标上没有牛
                {
                    ++curAns;
                    cerr << a << ":" << b << ":" << curAns << "\n";
                    continue;
                }

                //准备正方形需要的数据

                vector<int> yLowVec;   //在正方形内，低于bottom的牛,在lo和bottom之间的牛,存放y坐标
                vector<int> yHightVec; //在正方形内，高于top的牛，在top和hi之间，存放y坐标

                for (auto it = ySet.begin(); it != ySet.end(); ++it)
                {
                    int currY = (*it);
                    if (currY >= lo && currY < bottom)
                        yLowVec.push_back(currY);

                    if (currY > top && currY <= hi)
                        yHightVec.push_back(currY);
                }

                if (yLowVec.empty() && yHightVec.empty()) //在正方形移动范围内没有牛
                {
                    ++curAns;
                    cerr << a << ":" << b << ":" << curAns << "\n";
                    continue;
                }

                //向上移动正方形，使得每次下边界有牛消失或上边界有牛进入，或者两个同时有
                //在ySetLow和ySetHight跳跃
                auto lowCow = yLowVec.begin();
                auto higCow = yHightVec.begin();

                //判断正方形上下边是否有牛，有就计算重复数，旋转90度会重复
                auto checkRepeat=[&]()
                {
                    if (lowCow != yLowVec.end() && (*lowCow) - lo == 0) //最底低边是否有牛
                        ++repeat;
                    else if (lo == bottom)                                  //最底低已经达到hi
                        ++repeat;                    
                };
                
                checkRepeat();

                while (true)
                {
                    ++curAns;

                    int downDist = lowCow == yLowVec.end() ? INF : (*lowCow) - lo;  //底部指针离最近的牛的距离
                    int upDist = higCow == yHightVec.end() ? INF : (*higCow) - top; //顶部部指针离最近的牛的距离

                    if (downDist == INF && upDist == INF)
                    {
                        break;
                    }
                    else
                    {
                        //移动到最近的牛，按上下距离最小值
                        lo +=min(downDist + 1,upDist);
                        if (downDist + 1 < upDist)  //下面牛消失，上面牛无进入
                        {
                            ++lowCow;           
                        }
                        else if (downDist + 1 == upDist)    //下面牛消失同时上面牛进入
                        {
                            ++lowCow;
                            ++higCow;

                            //判断正方形上下边是否有牛，旋转90度会重复
                            checkRepeat();
                        }
                        else                                //下面牛无消失，上面牛进入
                        {
                            ++higCow;

                            //判断正方形上下边是否有牛，旋转90度会重复
                            checkRepeat();
                        }
                    }
                    top = lo + squareLen;   //同时移动top
                }

                cerr << a << ":" << b << ":" << curAns << "\n";
            }
        }
        return curAns;
    }

  public:
    void solve()
    {
        cin >> n;

        int ans = n + 1;
        cows = vector<pair<int, int>>(n);
        for (int i = 0; i <= n - 1; ++i)
            cin >> cows[i].x >> cows[i].y;
        ans += sum();

        //转90度
        for (int i = 0; i <= n - 1; ++i)
            swap(cows[i].x, cows[i].y);
        ans += sum();
        
        assert(repeat % 2 == 0);
        cout << ans - repeat / 2 << "\n";
        
    }
};

signed main()
{
    FastIO;

#ifdef LOCAL_DEBUG
    freopen("SquarePasture.in", "r", stdin);
    //freopen("SquarePasture.out", "w", stdout);
    auto startTime = chrono::high_resolution_clock::now();
#endif

    solution sln1;
    sln1.solve();
    cout.flush();

#ifdef LOCAL_DEBUG
    cerr << "Execution time: "
         << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - startTime).count()
         << " ms\n";
#endif

    return 0;
}

Contents

题目来源

题意

初步想法

进一步思路

队列(queue)版本 （双队列）

vector版本（双指针）

队列(queue)版本（双队列）