这题可能有很多种奇奇怪怪的做法X
这里主要是介绍下 std 的做法，相比其它做法应该会简单和好写许多
（波兰语真难读）
参考 - P149
解析
首先题意可以转化为，按给出的顺序添加圆（士兵），维护它们的交集，当交集首次为空时输出已添加的圆的数量（不含最后添加的那个圆）
设已添加的圆 K
1
,K
2
,⋯K
n
，即我们要维护交集 S=K
1
∩K
2
∩⋯∩K
n
考虑维护当前交集最右（x 坐标最大）的那个点，设其为 X
不难发现，当 S 不为空时，X 有如下性质：
引理 1. X 一定存在且唯一
引理 2. X 一定为某两个圆的交集 K
i
∩K
j
的最右点（可以有 i=j）
1. 的其中一种证明方式为，先证明交集是凸的，再根据圆的性质讨论即可。具体讨论此处略过
2. 的证明也是很显然的。首先 X 不可能不在任何圆的边缘上，否则我们只需单纯地增大 X 的 x 坐标就能得到一个更右边的点。如果 X 在某个圆 K
i
的边缘上，这意味着：
X 为 K
i
的最右点
存在另一个圆 K
j
，使得 X 为交集 K
i
∩K
j
的最右点
的至少其中之一满足。不然的话一定存在某个圆 K
k
，只要我们沿 K
k
的边缘增大 X 的 x 坐标就能得到矛盾。注意到这两个条件和 2. 是等价的，于是由此导出了 2. 的证明
设集合 P 由所有可能的两个圆的交 K
i
∩K
j
的最右点构成。接着还能注意到：
引理 3. X 一定为 P 中 x 坐标最小的那个点
证明只需考虑圆的性质、交集的基本性质以及 1. 即可
由此问题就已经转化成，检查一个特定的点——集合 P 最左边的点——是否在当前的所有圆中（S 是否为空）。P 比 S 更容易描述和计算；要做到这点，我们只需在每添加一个圆时简单地 O(n) 维护集合 P（求两个圆的交的最右点是可以 O(1) 做到的，但具体此处略过）与检查 P 最左边的点是否合法。算法总的复杂度是 O(n
2
) 的
代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#define nan 0.0/0
#define double long double
using stdvector;
using stdmax;
const double eps =1e-14;
struct point{
double x, y;
};
struct circle{
point O;
double r;
};
const point Null(nan, nan);
bool inCircle(const point &x, const circle &K){
// return (sqrt((x.x-K.O.x)(x.x-K.O.x)+(x.y-K.O.y)(x.y-K.O.y)) < K.r);
return ((x.x-K.O.x)(x.x-K.O.x)+(x.y-K.O.y)(x.y-K.O.y) <= K.r*K.r+1e-7);
}
// 返回两个圆交集的 x 坐标最大点 //
point prawyPunkt(const circle &K1, const circle &K2){
if((K1.O.x-K2.O.x)(K1.O.x-K2.O.x)+(K1.O.y-K2.O.y)(K1.O.y-K2.O.y) < (K1.r-K2.r)*(K1.r-K2.r)+eps){ // 包含的情况 //
if((K1.O.x+K1.r <= K2.O.x+K2.r+eps && K1.O.x-K1.r >= K2.O.x-K2.r-eps) && (K1.O.y+K1.r <= K2.O.y+K2.r+eps && K1.O.y-K1.r >= K2.O.y-K2.r-eps))
return point(K1.O.x+K1.r, K1.O.y);
else if((K2.O.x+K2.r <= K1.O.x+K1.r+eps && K2.O.x-K2.r >= K1.O.x-K1.r-eps) && (K2.O.y+K2.r <= K1.O.y+K1.r+eps && K2.O.y-K2.r >= K1.O.y-K1.r-eps))
return point(K2.O.x+K2.r, K2.O.y);
}
else{ // 求两圆交点；下面的式子事实上都是用 matlab 推的，所以别试着搞懂 ( //
double a1 =K1.O.x, b1 =K1.O.y, R1 =K1.r, a2 =K2.O.x, b2 =K2.O.y, R2 =K2.r;
}
int main(){
int n;
scanf("%d", &n);
vector<circle> arr(n);
point x(0, 0);
for(int i =0; i < n; ++i){
int _x, _y, _r;
scanf("%d%d%d", &_x, &_y, &_r);
arr[i] =circle(_x, _y, _r);
}
