「SCOI2016」妖怪 - 凸包+双勾函数极值

题目大意

    邱老师是妖怪爱好者，他有$n$只妖怪，每只妖怪有攻击力$\text{atk}$和防御力$\text{dnf}$两种属性。
    邱老师立志成为妖怪大师，于是他从真新镇出发，踏上未知的旅途，见识不同的风景。
    环境对妖怪的战斗力有很大影响，在某种环境中，妖怪可以降低自己$k\times a$点攻击力，提升$k\times b$点防御力或者，提升自己$k\times a$点攻击力，降低$k\times b$点防御力，$a,b$属于正实数，$k$为任意实数，但是$\text{atk}$和$\text{dnf}$必须始终非负。
    妖怪在环境$(a,b)$中的战斗力为妖怪在该种环境中能达到的最大攻击力和最大防御力之和。

$$\text{strength}(a,b)=\max(\text{atk}(a,b))+\max(\text{dnf}(a,b))$$

    环境由$a,b$两个参数定义，$a,b$的含义见前文描述。
    比如当前环境$a=3,b=2$，那么攻击力为$6$，防御力为$2$的妖怪，能达到的最大攻击力为$9$，最大防御力为$6$。所以该妖怪在$a=3,b=2$的环境下战斗力为$15$。
    因此，在不同的环境，战斗力最强的妖怪可能发生变化。作为一名优秀的妖怪训练师，邱老师想发掘每一只妖怪的最大潜力，他想知道在最为不利的情况下，他的$n$只妖怪能够达到的最强战斗力值，即存在一组正实数$(a,b)$使得$n$只妖怪在该环境下最强战斗力最低。

---

题目分析

一些感想

• 这本来是一道很有意思的题目，可是很多人直接用二分水过了，这就没有意思了。
• LZX：“二分这么好。” Bill：“我的算法是线性的。”
• LZX：“二分这么短。” Bill：“我的代码比你短。”
• LZX：“二分好写。” Bill：“好吧你赢了。”

将$(\text{atk},\text{dnf})$记作二维坐标$(x_0,y_0)$。
题目的环境变量$(a,b)$对$(x_0,y_0)$的影响记作坐标$(x,y)$。
$(x,y)$可以取到的轨迹形成直线：

$$l:bx+ay+c=0$$

整理为斜截式可得：

$$l:y=-\frac bax-c$$

故斜率$k=-\frac ba$。

（图片来自a_crazy_czy）

因为斜率为负，不难发现最强的妖怪一定在右上凸包上。
（图片来自a_crazy_czy）
如上图，每个点能取到最小值的斜率有一定的角度区间限制。

代入点$(x_0,y_0)$：

$$bx_0+ay_0+c=0$$

故，

$$l:b(x-x_0)+a(y-y_0)=0$$

取$x=0$或$y=0$即可算出力量值：

$$\begin{aligned} \text{strength}&=\frac bax_0+y_0+\frac aby_0+x_0 \\ &=\frac bax_0+\frac aby_0+x_0+y_0 \end{aligned}$$

令$t=\frac ba$，注意$k=-t$，故：

$$\text{strength}=tx_0+\frac 1ty_0+x_0+y_0$$

注意到这是一个双勾函数，$t$在$\sqrt{\frac{y_0}{x_0}}$取到最小值，再结合上面的角度区间限制更新答案即可。

时间复杂度$O(n)$。

---

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=1000005;

struct Point {
	LL x,y;
	Point(LL x=0,LL y=0):x(x),y(y) {}
	Point operator - (const Point &b) {return Point(b.x-x,b.y-y);}
	bool operator < (const Point &b) const {return x<b.x||(x==b.x&&y<b.y);}
} p[maxn],S[maxn];

typedef Point Vector;

LL Cross(Vector a,Vector b) {return a.x*b.y-b.x*a.y;}
double Slope(Point a,Point b) {return 1.0*(b.y-a.y)/(b.x-a.x);}
double Optimalk(Point p) {return -sqrt(1.0*p.y/p.x);}
double Cal(Point p,double k) {return k>=0?1e18:p.x+p.y-p.x*k-p.y/k;}

int n,top=0;
double ans=1e18;

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++) {
		p[i].x=Get_Int();
		p[i].y=Get_Int();
	}
	sort(p+1,p+n+1);
	for(int i=1; i<=n; i++) {
		while(top>1&&Cross(S[top-1]-S[top],S[top-1]-p[i])>=0)top--;
		S[++top]=p[i];
	}
	if(top==1) {printf("%0.4lf\n",Cal(S[1],Optimalk(S[1])));return 0;}
	double r=Slope(S[1],S[2]),k=Optimalk(S[1]);
	if(k>=r)ans=min(ans,Cal(S[1],k));
	else ans=min(ans,Cal(S[1],r));
	double l=Slope(S[top-1],S[top]);k=Optimalk(S[top]);
	if(k<=l)ans=min(ans,Cal(S[top],k));
	else ans=min(ans,Cal(S[top],l));
	for(int i=2; i<top; i++) {
		l=Slope(S[i-1],S[i]),r=Slope(S[i],S[i+1]),k=Optimalk(S[i]);
		if(k>=l&&k<=r)ans=min(ans,Cal(S[i],k));
		else ans=min(ans,min(Cal(S[i],l),Cal(S[i],r)));
	}
	printf("%0.4lf\n",ans);
	return 0;
}