1 条题解
-
0
题目大意
有 个互不相交的圆(可以相切),第 个圆圆心为 ,半径为 ,求这些圆平面分成了几个部分。
题解
据我所知,本题共有 个做法。
Sol1. 单调栈
首先,我们观察到每加入一个圆,至少多分了 个部分,但也有时候分成了两个部分,即大圆被若干个小圆分成上下两部分。
那么我们考虑如何统计这种特殊情况。
首先,我们按每个圆的右端点从小到大排序,然后,我们按顺序加入单调栈中。
那么如果一个大圆里面的小圆没有再包含一个圆,我们就可以直接记录这个大圆包含的小圆的直径和,与大圆的直径比较就可以判断是否为特殊情况。
那么我们考虑维护一个没有包含关系的栈。
因为我们把右端点从小到大排了序,所以在加入一个圆的时候,我们只要看左端点,如果刚加的这个圆的左端点小于等于栈顶的左端点,那么栈顶的圆就被包含了,我们把它弹出,顺便记录弹出圆的直径和。
于是我们这个左端点递增的单调栈,既可以保证没有二次包含关系,也可以实时统计大圆包含的小圆的直径和,直接判断即可。
时间复杂度为 ,瓶颈在排序上。
#include <bits/stdc++.h> using namespace std; #define ll long long #define PII pair<int, int> #define mkp make_pair #define INF INT_MAX template <typename T> inline void rd(T &x){ x = 0; bool f = true; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = false; ch = getchar();} while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();} if(!f) x = -x; } template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);} const int N = 3e5 + 10; struct circle { int x, r; }c[N]; bool cmp(circle A, circle B) { if(A.x + A.r != B.x + B.r) return A.x + A.r < B.x + B.r; else return A.x - A.r > B.x - B.r; } int n, st[N], top, ans; int main() { // freopen(".in", "r", stdin); // freopen(".out", "w", stdout); rd(n); for(int i = 1; i <= n; ++i) rd(c[i].x, c[i].r); sort(c + 1, c + n + 1, cmp); for(int i = 1; i <= n; ++i) { int now = c[i].x - c[i].r, sum = 0; while(c[st[top]].x - c[st[top]].r >= now && top >= 1) { sum += 2 * c[st[top]].r; top --; } st[++top] = i; if(sum == 2 * c[i].r) ans ++; } cout << ans + n + 1 << endl; return 0; }
Sol2.并查集
首先回到统计大圆被小圆分割成上下两个部分的情况数。
我们如果在按半径加入圆的时候,把它的左右端点连一条边,那么在加入大圆的时候,如果大圆的左右端点已经连通了,那么这个大圆一定被小圆分割成上下两部分了。
因为坐标很大,并且可能是负数,所以离散化后并查集即可。
复杂度为 。
Sol3.线段树
继续回到统计大圆被小圆分割成上下两个部分的情况数。
按半径加入圆的时候,我们在这个圆的两个端点进行一次区间
+1
,那么如果大圆左右端点的区间的区间最小值为0
,那说明没有被完全分开,否则被完全分开。这里依然要离散化。
复杂度为 。
注意,Sol2 和 Sol3 中的做法需要注意,线段树和并查集只能维护整点的信息,所以我们将左端点 +1,或者右端点 -1,来保证不会有形如 在一个圆, 在另一个圆,就算中间有空隙,也不会被计算到的情况。
线段树代码:Paste。
- 1
信息
- ID
- 5775
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- 5
- 标签
- 递交数
- 5
- 已通过
- 2
- 上传者