[Luogu P3291] [BZOJ 3570] [SCOI2016]妖怪

洛谷传送门

BZOJ传送门

题目描述

邱老师是妖怪爱好者，他有$n$n只妖怪，每只妖怪有攻击力atk和防御力dnf两种属性。邱老师立志成为妖怪大师，于是他从真新镇出发，踏上未知的旅途，见识不同的风景。

环境对妖怪的战斗力有很大影响，在某种环境中，妖怪可以降低自己$k*a$k∗a点攻击力，提升$k*b$k∗b点防御力或者，提升自己$k*a$k∗a点攻击力，降低$k*b$k∗b点防御力，$a$a，$b$b属于正实数，$k$k为任意实数，但是atk和dnf必须始终非负。

妖怪在环境$(a,b)$(a,b)中的战斗力为妖怪在该种环境中能达到的最大攻击力和最大防御力之和。$strength(a,b)=max(atk(a,b))+max(dnf(a,b))$strength(a,b)=max(atk(a,b))+max(dnf(a,b))环境由$a$a，$b$b两个参数定义，$a$a，$b$b的含义见前文描述。

比如当前环境$a=3$a=3，$b=2$b=2，那么攻击力为$6$6，防御力为$2$2的妖怪，能达到的最大攻击力为$9$9，最大防御力为$6$6。所以该妖怪在$a=3$a=3，$b=2$b=2的环境下战斗力为$15$15。

因此，在不同的环境，战斗力最强的妖怪可能发生变化。

作为一名优秀的妖怪训练师，邱老师想发掘每一只妖怪的最大潜力，他想知道在最为不利的情况下，他的$n$n只妖怪能够达到的最强战斗力值，即存在一组正实数$(a,b)$(a,b)使得$n$n只妖怪在该环境下最强战斗力最低。

输入输出格式

输入格式：

第一行一个$n$n，表示有$n$n只妖怪。

接下来$n$n行，每行两个整数atk和dnf，表示妖怪的攻击力和防御力。$1\le n\le 10^6, 0＜atk, dnf\le 10^8$1≤n≤106,0＜atk,dnf≤108

输出格式：

输出在最不利情况下最强妖怪的战斗力值，保留$4$4位小数。

输入输出样例

输入样例#1：

3
1 1
1 2
2 2

输出样例#1：

8.0000

解题分析

题目就是要我们求下面这个式子：
$min(max_{i=1}^{n}(x+y+\frac{b}{a}x+\frac{a}{b}y))$min(maxi=1n​(x+y+ab​x+ba​y))
设$k=\frac{b}{a}$k=ab​， 那么后面那个式子就变成了$x+y+kx+\frac{y}{k}$x+y+kx+ky​。

这是个啥玩意呢？ 画出平面直角坐标系可以发现这玩意就是斜率为$-k$−k， 经过点$(x,y)$(x,y)的直线在$x$x和$y$y轴上的截距之和。

然后发现可能成为最大值的点一定在一个上凸包上， 搞一搞就好。

由均值不等式可得这个函数的最小值在$k=\sqrt \frac{y}{x}$k=xy​​处取到， 这个点成为最大值的区间就是相邻两条线段的斜率之间的部分， 判一判是不是在这个区间内就好了。

注意右上凸包两端的点的横纵坐标分别加上EPS， 避免出现nan的情况。

代码如下：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <iostream>
#include <algorithm>
#define R register
#define IN inline
#define W while
#define db long double
#define MX 1000050
#define EPS 1e-8
template <class T> IN T max(T a, T b) {return a > b ? a : b;}
template <class T> IN T min(T a, T b) {return a < b ? a : b;}
int n, cnum;
int conv[MX];
struct Point {db x, y;}dat[MX];
IN Point operator + (const Point &x, const Point &y) {return {x.x + y.x, x.y + y.y};}
IN Point operator - (const Point &x, const Point &y) {return {x.x - y.x, x.y - y.y};}
IN db operator * (const Point &x, const Point &y) {return x.x * y.y - x.y * y.x;}
IN bool operator < (const Point &x, const Point &y) {return x.x == y.x ? x.y > y.y : x.x < y.x;}
IN db Getk(const Point &x) {return x.y / x.x;}
IN void Getconv()
{
	std::sort(dat + 1, dat + 1 + n);
	for (R int i = 1; i <= n; ++i)
	{
		W (cnum >= 2 && (dat[conv[cnum]] - dat[conv[cnum - 1]]) * (dat[i] - dat[conv[cnum - 1]]) >= 0) --cnum;
		conv[++cnum] = i;
	}
}
int main(void)
{
	db mxx = 0, mxy = 0, ratl, ratr, best;
	scanf("%d", &n);
	for (R int i = 1; i <= n; ++i)
	{
		scanf("%Lf%Lf", &dat[i].x, &dat[i].y);
		mxx = max(mxx, dat[i].x), mxy = max(mxy, dat[i].y);
	}
	dat[++n] = {0, mxy}, dat[++n] = {mxx, 0};
	Getconv(); db ans = 1e18;
	dat[conv[cnum]].x += EPS;
	dat[conv[1]].y += EPS;
	for (R int i = 2; i < cnum; ++i)
	{
		ratl = -Getk(dat[conv[i]] - dat[conv[i - 1]]);
		ratr = -Getk(dat[conv[i + 1]] - dat[conv[i]]);
		ans = min(ans, dat[conv[i]].x + dat[conv[i]].y + ratl * dat[conv[i]].x + dat[conv[i]].y / ratl);
		ans = min(ans, dat[conv[i]].x + dat[conv[i]].y + ratr * dat[conv[i]].x + dat[conv[i]].y / ratr);
		best = std::sqrt(dat[conv[i]].y / dat[conv[i]].x);
		if (best >= ratl && best <= ratr) ans = min(ans, dat[conv[i]].x + dat[conv[i]].y + best * dat[conv[i]].x + dat[conv[i]].y / best);
	}
	printf("%.4Lf", ans);
}