BZOJ2642 Pku3968 Jungle Outpost

看mhy写了好几天了啊。然后研究了一下，居然过得比他早。

首先敌人一定可以炸连续的一段。然后就是要看炸掉任意连续一段之后还有没有剩下的公共部分，既半平面交。

然后我yy出了一个半平面交的做法。找出一条基准直线，按方向顺时针方向排序。然后按照正常半平面交的方法根据栈顶两个元素和当前直线的位置关系判断是否需要退栈。然后当找到一条与基准直线的角度大于等于π的直线（直线是有向的，也可以说是成负角）且它把栈里退到只剩基准直线一条的时候，这些半平面没有交。否则这些半平面有交。

至于证明嘛，我也不会（挠头），毕竟是感受出来的。然后感觉这次代码写得比较漂亮，开心。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

inline double sqr(double x) {
	return x * x;
}

struct point {
	double x, y;
	inline point() {}
	inline point(double x0, double y0) {
		x = x0, y = y0;
	}
	inline void read() {
		scanf("%lf%lf", &x, &y);
	}
};
struct vect {
	double x, y;
	inline vect() {}
	inline vect(double x0, double y0) {
		x = x0, y = y0;
	}
	inline vect(point a, point b) {
		x = b. x - a. x, y = b. y - a. y;
	}
	inline vect vertical() {
		return vect(y, - x);
	}
	inline double length() {
		return sqrt(sqr(x) + sqr(y));
	}
};
struct line {
	point a;
	vect d;
	inline line() {}
	inline line(point u, point v) {
		a = u;
		d = vect(u, v);
	}
};

const double eps = 1e-8;

inline point operator +(const point& a, const vect& b) {
	return point(a. x + b. x, a. y + b. y);
}
inline double operator *(const vect& a, const vect& b) {
	return a. x * b. y - a. y * b. x;
}
inline vect operator *(const vect& a, double r) {
	return vect(a. x * r, a. y * r);
}
inline int sgn(double x) {
	return (fabs(x) < eps) ? 0 : ((x > 0) ? 1 : -1);
}

const int maxn = 50009;

int n, t, li[maxn], tst;
point a[maxn], b[maxn];
line l[maxn];

inline bool outSide(line l, point p) {
	return sgn(vect(l. a, p) * l. d) <= 0;
}

point getCross(line l1, line l2) {
	point a(l1. a), b(l1. a + l1. d);
	point c(l2. a), d(l2. a + l2. d);
	if (!sgn(vect(d, c) * vect(d, b))) {
		d = l2. a + l2. d * 2.0;
		b = l1. a + l1. d * 2.0;
	}
	if (!sgn(vect(d, a) * vect(d, c)))
		a = l1. a + l1. d * 3.0;
	double sa(vect(d, a) * vect(d, c));
	double sb(vect(d, c) * vect(d, b));
	double rat(sa / (sa + sb));
	return point(a + vect(a, b) * rat);
}

bool check(int t) {
	for (int i = 0; i < n; ++ i)
		l[i] = line(a[i], a[(i + t + 1) % n]);
	tst = 2;
	li[1] = 0;
	b[2] = getCross(l[0], l[1]);
	li[2] = 1;
	for (int i = 2; i < n; ++ i) {
		while (tst > 1 && outSide(l[i], b[tst]))
			-- tst;
		if (tst == 1 && sgn(l[i]. d * l[0]. d) <= 0)
			return 0;
		li[++ tst] = i;
		b[tst] = getCross(l[li[tst - 1]], l[i]);
	}
	return tst > 2;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d", &n);
	for (int i = 0; i <	n; ++ i)
		a[i]. read();
	int l(1), r(n - 2);
	while (l < r) {
		int mid((l + r) >> 1);
		if (check(mid))
			l = mid + 1;
		else
			r = mid;
	}
	printf("%d\n", l);
}

顺便把写的画图的js粘上来好了。以后说不定还有用。