生活随笔
收集整理的這篇文章主要介紹了
2021牛客暑期多校训练营6 Hopping Rabbit 扫描线 + 矩形 + 细节
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
傳送門
文章目錄
題意：
給你nnn個矩形，以及一個距離ddd，讓你找一個點(diǎn)(x+0.5,y+0.5)(x+0.5,y+0.5)(x+0.5,y+0.5)，這個點(diǎn)一次能向四個方向跳ddd的距離，這個點(diǎn)不管怎么跳都跳不到矩形內(nèi)。輸出(x,y)(x,y)(x,y)。
n,d≤1e5,?1e9≤x,y≤1e9n,d\le1e5,-1e9\le x,y\le1e9n,d≤1e5,?1e9≤x,y≤1e9
思路：
看了半天樣例看懂了題，讓后改對了。
將所有矩形移動到[0,d][0,d][0,d]內(nèi)，這個可以通過取模來實(shí)現(xiàn)，一個矩形移動到[0,d][0,d][0,d]內(nèi)后最多形成444個矩形，之后我們在矩形內(nèi)找一個空位置就是答案了。
考慮用掃描線來解決上述問題，將區(qū)間轉(zhuǎn)換為點(diǎn)，可以將x2??,y2??x2--,y2--x2??,y2??，之后加入形成的矩形，讓后掃的時候判斷當(dāng)前列是否滿，非滿的話直接lognlognlogn找到位置輸出即可。
代碼還是很好寫的，主要是弄清楚題以及邊界問題。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=1e9;
const double eps
=1e-6;int n
,d
;
struct Node {int l
,r
;int cnt
,sum
;
}tr
[N
<<2];
struct Query {int y1
,y2
,op
;
};
vector
<PII
>x
,y
;
vector
<Query
>a
[N
];void pushup(int u
) {if(tr
[u
].cnt
) tr
[u
].sum
=Len(u
);else if(tr
[u
].l
==tr
[u
].r
) tr
[u
].sum
=0;else tr
[u
].sum
=tr
[L
].sum
+tr
[R
].sum
;
}void build(int u
,int l
,int r
) {tr
[u
]={l
,r
,0,0};if(l
==r
) return;build(L
,l
,Mid
); build(R
,Mid
+1,r
);
} void change(int u
,int l
,int r
,int x
) {if(l
>r
) return;if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
) {tr
[u
].cnt
+=x
;pushup(u
);return;}int mid
=(l
+r
)>>1;if(l
<=Mid
) change(L
,l
,r
,x
);if(r
>Mid
) change(R
,l
,r
,x
);pushup(u
);
} int find(int u
) {if(tr
[u
].l
==tr
[u
].r
) return tr
[u
].l
;if(tr
[L
].sum
<Len(L
)) return find(L
);else return find(R
);
} int find() {if(tr
[1].sum
>=d
) return -1;return find(1);
}int main()
{
scanf("%d%d",&n
,&d
);for(int i
=1;i
<=n
;i
++) {int x1
,y1
,x2
,y2
; scanf("%d%d%d%d",&x1
,&y1
,&x2
,&y2
);bool flag1
,flag2
; flag1
=flag2
=false;if(x2
-x1
>=d
) flag1
=true;if(y2
-y1
>=d
) flag2
=true;x2
--; y2
--;x1
%=d
; x2
%=d
; y1
%=d
; y2
%=d
;x1
+=d
; x2
+=d
; y1
+=d
; y2
+=d
;x1
%=d
; x2
%=d
; y1
%=d
; y2
%=d
;x
.clear(); y
.clear();if(flag1
) x
.pb({0,d
});else if(x1
<=x2
) x
.pb({x1
,x2
});else x
.pb({x1
,d
}),x
.pb({0,x2
});if(flag2
) y
.pb({0,d
});else if(y1
<=y2
) y
.pb({y1
,y2
});else y
.pb({y1
,d
}),y
.pb({0,y2
});for(auto xx
:x
) {for(auto yy
:y
) {a
[xx
.X
].pb({yy
.X
,yy
.Y
,1});a
[xx
.Y
+1].pb({yy
.X
,yy
.Y
,-1});}}}build(1,0,d
-1);for(int i
=0;i
<d
;i
++) {for(auto x
:a
[i
]) {change(1,x
.y1
,x
.y2
,x
.op
);}int pos
=find();if(pos
!=-1) {puts("YES");cout
<<i
<<' '<<pos
<<endl
;return 0;}}puts("NO");return 0;
}
總結(jié)
以上是生活随笔為你收集整理的2021牛客暑期多校训练营6 Hopping Rabbit 扫描线 + 矩形 + 细节的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
