TIOJ 2054
題敘
https://tioj.ck.tp.edu.tw/problems/2054
二維 slide window 問題
給定一個長方形的寬與高，以及一個平面座標上的多個點座標
問該長方形最多能涵蓋多少點座標
想法
如果是一維的，也就是長方形的高是無限大的情況
我們只需要維護左界與右界，每次看看下一個點加入後右界與左界的距離有沒有超過寬
只需要 $O(N)$ 就可以知道最多有多少點了
那如果今天的情況是長方形的寬是無限大的情況呢?
同樣，我們也只需要維護左界與右界，每次看看下一個點加入後右介宇左界的距離有沒有超過高
同樣只需要 $O(N)$ 就可以知道有多少點
今天的狀況是二維，概念仍然相同
我們先將座標們以x座標優先，y座標其次的排序
在維護左右界的同時，也看看這些座標依照y座標優先，x座標其次的排序後，哪些還符合
同樣掃過去即可
Code
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
|
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define pii pair<int,int>
using namespace std;
int n,l,w;
vector<pii> v;
int solve(){
int res=0;
for(int L=0,R=0 ; L<n && R<n ; ){
if(L==R){
res=max(res,1);
R++;
}
else if(v[R].first-v[L].first>w){
L++;
}
else{
vector<pii> tmp;
for(int i=L ; i<=R ; i++){
tmp.emplace_back(v[i].second,v[i].first);
}
sort(tmp.begin(),tmp.end());
int m=tmp.size();
for(int D=0,T=0 ; D<m && T<m ; ){
if(D==T){
T++;
}
else if(tmp[T].first-tmp[D].first>l){
D++;
}
else{
res=max(res,T-D+1);
T++;
}
}
R++;
}
}
return res;
}
int main(){
IOS;
cin>>n>>l>>w;
for(int i=0,x,y ; i<n ; i++){
cin>>x>>y;
v.emplace_back(x,y);
}
sort(v.begin(),v.end());
cout<<solve()<<'\n';
return 0;
}
|
複雜度
橫向與直向皆約為 $O(N)$
總複雜度 $O(N^2)$