【笔记】计算几何

% 经典问题

%.1 平面最近点对

分治是容易想到的。主要是合并，如果我们要更优，那么一定比左右两个子区间更优，所以我们初步框定了每个点最多能产生贡献的点集，而这个点集内部的两个点，如果同属一个子区间，那么之间的距离必定天然满足大于等于该子区间的最优答案，所以实际上我们框定范围内的点就很少了，直接暴力更新答案就好。

template

struct point {
	double x, y;
	friend istream& operator >> (istream& in, point& p) { return in >> p.x >> p.y; }
	friend ostream& operator << (ostream& out, point& p) { return out << '(' << p.x << ',' << p.y << ") "; }
	point operator + (point p) { return {x+p.x, y+p.y}; };
	point operator - (point p) { return {x-p.x, y-p.y}; };
	point operator * (double t) { return {x*t, y*t}; };
	double operator ^ (point p) { return x*p.x + y*p.y; };  // 点积
	double operator & (point p) { return x*p.y - y*p.x; };  // 叉积
};
double dist (point x, point y) {
	return sqrt((x.x-y.x)*(x.x-y.x) + (x.y-y.y)*(x.y-y.y));
}
typedef point vec;
struct segment {
	point s, t;
	friend istream& operator >> (istream& in, segment& p) { return in >> p.s >> p.t; }
};
struct polygon {
	vector<point> a;
	friend ostream& operator << (ostream& out, polygon& p) {
		for (point i : p.a) out << i; return out;
	}
} sec[N];
bool is_inner (point p, polygon& x) {
	for (int i = 1; i < x.a.size(); i++)
		if (((x.a[i-1]-p) * (x.a[i]-p)) <= 0)
			return 0;
	return ((x.a.back()-p) * (x.a[0]-p)) >= 0;
}
bool is_intersect (segment a, segment b) {  // 不考虑共线的情况
	point A = a.s, B = a.t, C = b.s, D = b.t;
	vec AB = B-A, AC = C-A, AD = D-A;
	vec CD = D-C, CA = A-C, CB = B-C;
    return (AB & AC) * (AB & AD) < -eps && (CD & CA) * (CD & CB) < -eps;
}