【BZOJ 4570】【SCOI 2016】妖怪

http://www.lydsy.com/JudgeOnline/problem.php?id=4570

对于每个妖怪的两个值，看成二位平面上的一个点的横纵坐标(x,y)。

因为只关心a/b，所以设经过这个点的斜率为k，那么妖怪的战斗力为\(x+y-kx-\frac yk\)。

对于一个k，要找所有妖怪的战斗力的最大值，只要在这些点的凸壳上查找就可以了。

对于凸壳上的每个点，检查这个点的战斗力最小时的斜率k会不会影响周围的两个点再更新，最后再统计凸壳上相邻两点的斜率来更新就可以了。

时间复杂度\(O(n\log n)\)。

关于战斗力，斜率之类的式子一定不能推错啊！

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 1000003;

struct Point {

	double x, y;

	Point (double _x = 0, double _y = 0) : x(_x), y(_y) {}

	Point operator - (const Point &A) const {

		return Point(x - A.x, y - A.y);

	}

	bool operator < (const Point &A) const {

		return x == A.x ? y > A.y : x > A.x;

	}

} P[N];

double Cross(const Point &A, const Point &B) {

	return (A.x * B.y - A.y * B.x) > 1e-8 ? 1 : -1;

}

int n, id[N];

double K(const int &a, const int &b) {return (P[b].y - P[a].y) / (P[b].x - P[a].x);}

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; ++i)

		scanf("%lf%lf", &P[i].x, &P[i].y);

	stable_sort(P + 1, P + n + 1);

	int top = 1;

	id[1] = 1;

	for (int i = 2; i <= n; ++i) {

		while (top > 1 && Cross(P[i] - P[id[top]], P[id[top]] - P[id[top - 1]]) >= 0) --top;

		id[++top] = i;

	}

	while (top > 1 && (P[id[top]].y <= P[id[top - 1]].y)) --top;

	double k, ans = 1e20;

	for (int i = 1; i <= top; ++i) {

		k = -sqrt(1.0 * P[id[i]].y / P[id[i]].x);

		if ((i == 1 || K(id[i - 1], id[i]) < k) && (i == top || K(id[i], id[i + 1]) > k))

			ans = min(ans, P[id[i]].x + P[id[i]].y + 2.0 * sqrt(P[id[i]].x * P[id[i]].y));

	}

	for (int i = 1; i < top; ++i) {

		k = K(id[i], id[i + 1]);

		ans = min(ans, P[id[i]].x + P[id[i]].y - P[id[i]].x * k - P[id[i]].y / k);

	}

	printf("%.4lf\n", ans);

	return 0;

}