关于此题的std的做法

这题可能有很多种奇奇怪怪的做法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;

point(){}
point(const double &_x, const double &_y)
	:x(_x), y(_y){}

inline bool Null() const{
	return (x != x || y != y);
}

};
struct circle{
point O;
double r;

circle(){}
circle(const double &_x, const double &_y, const double &_r)
	:O(point(_x, _y)), r(_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;

	double R1R1 =R1*R1;
	double a1a1 =a1*a1;
	double b1b1 =b1*b1;

	double a2a2 =a2*a2;
	double b2b2 =b2*b2;
	double R2R2 =R2*R2;

	double subs1 = a1a1 - 2 * a1*a2 + a2a2 + b1b1 - 2 * b1*b2 + b2b2;
	double subs2 = -R1R1 * a1 + R1R1 * a2 + R2R2 * a1 - R2R2 * a2 + a1a1*a1 - a1a1 * a2 - a1*a2a2 + a1*b1b1 - 2 * a1*b1*b2 + a1*b2b2 + a2a2*a2 + a2*b1b1 - 2 * a2*b1*b2 + a2*b2b2;
	double subs3 = -R1R1 * b1 + R1R1 * b2 + R2R2 * b1 - R2R2 * b2 + a1a1*b1 + a1a1 * b2 - 2 * a1*a2*b1 - 2 * a1*a2*b2 + a2a2 * b1 + a2a2 * b2 + b1b1*b1 - b1b1 * b2 - b1*b2b2 + b2b2*b2;
	double sigma = sqrt((R1R1 + 2 * R1*R2 + R2R2 - a1a1 + 2 * a1*a2 - a2a2 - b1b1 + 2 * b1*b2 - b2b2)*(-R1R1 + 2 * R1*R2 - R2R2 + subs1));
	
	if(abs(subs1) > eps){
		point P1, P2;
		P1.x = (subs2 - sigma*b1 + sigma*b2) / (2 * subs1);
		P2.x = (subs2 + sigma*b1 - sigma*b2) / (2 * subs1);
	
		P1.y = (subs3 + sigma*a1 - sigma*a2) / (2 * subs1);
		P2.y = (subs3 - sigma*a1 + sigma*a2) / (2 * subs1);
		
		point P =((P1.x > P2.x) ? P1 : P2);
		
		// 若不为交点，则为其中一个圆的最右点 //
		const point Q1 =point(K1.O.x+K1.r, K1.O.y);
		if(inCircle(Q1, K2) && Q1.x > P.x-eps)
			P =Q1;
		const point Q2 =point(K2.O.x+K2.r, K2.O.y);
		if(inCircle(Q2, K1) && Q2.x > P.x-eps)
			P =Q2;
		
		return P;
	}
	else
		return Null;
}

}

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);

	if(i == 1)
		x =prawyPunkt(arr[0], arr[1]);
	else if(i > 1){
		for(int j =0; j < i && !x.Null(); ++j){
			const point y =prawyPunkt(arr[i], arr[j]);
			if(y.Null() || y.x < x.x+eps)
				x =y;
		}
		for(int j =0; j <= i && !x.Null(); ++j)
			if(!inCircle(x, arr[j]))
				x =Null;
	}
	if(x.Null())
		return printf("%d", i+1) && 0;
}
puts("NIE");

}