SCOI2016 妖怪（三分+凸包）

发表于 |
字数统计: 1,249字 | 阅读时长 ≈ 6min

【Scoi2016】妖怪

问题描述

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

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

输入格式

第一行一个n，表示有n只妖怪。接下来n行，每行两个整数atk和dnf，表示妖怪的攻击力和防御力。

$1≤n≤10^6, 0＜atk,dnf≤10^8$

输出格式

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

样例输入

3

1 1

1 2

2 2

样例输出

8.0000

推导一下容易发现题目要求的就是$\frac{b}{a}x+y+\frac{a}{b}y+x$的最值。注意到$a,b$为正实数，不妨令$k=\frac{b}{a}$，那么所求即$f(k)=x+y+kx+\frac{1}{k}y$的最值，不难发现这是个下凸函数，那么直接三分$k$的值。这个方法需要反复实验才能通过。

再观察一下发现，当$k$为定值的时候，假设$x>x’$可以发现类似斜率优化的式子，得到有用的点一定是在上凸包上，因此可以先预处理凸包再三分。

代码（裸三分）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1000005
using namespace std;
const double eps=1e-12;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
int n,A[N],B[N];
inline double f(double x)
{
	double Max=-9e18,y=1/x;
	for(register int i=1;i<=n;i++)
	{
		double t=x*A[i]+y*B[i]+A[i]+B[i];
		Max=Max<t?t:Max;
	}
	return Max;
}
double DC(double l,double r)
{
	double res;
	while(r-l>=eps)
	{
		double lmid=l+(r-l)/3,lans=f(lmid);
		double rmid=r-(r-l)/3,rans=f(rmid);
		if(lans>rans)l=lmid,res=rans;
		else r=rmid,res=lans;
	}
	return res;
}
int main()
{
	_R(n);
	for(register int i=1;i<=n;i++)_R(A[i]),_R(B[i]);
	printf("%.4lf",DC(eps,10));
}

代码（凸包+三分）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1000005
#define ll long long
using namespace std;
const double eps=1e-12;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
struct node{int x,y;}P[N],S[N];
node operator+(node a,node b){return (node){a.x+b.x,a.y+b.y};}
node operator-(node a,node b){return (node){a.x-b.x,a.y-b.y};}
ll operator*(node a,node b){return 1ll*a.x*b.y-1ll*a.y*b.x;}
bool operator<(node a,node b)
{
	if(a.x!=b.x)return a.x>b.x;
	return a.y<b.y;
}
int n,top;
inline double f(double x)
{
	double Max=-9e18,y=1/x;
	for(register int i=1;i<=top;i++)
	{
		double t=x*S[i].x+y*S[i].y+S[i].x+S[i].y;
		Max=Max<t?t:Max;
	}
	return Max;
}
double DC(double l,double r)
{
	double res;
	while(r-l>=eps)
	{
		double lmid=l+(r-l)/3,lans=f(lmid);
		double rmid=r-(r-l)/3,rans=f(rmid);
		if(lans>rans)l=lmid,res=rans;
		else r=rmid,res=lans;
	}
	return res;
}
int main()
{
	_R(n);
	for(register int i=1;i<=n;i++)_R(P[i].x),_R(P[i].y);
	sort(P+1,P+n+1);
	for(register int i=1;i<=n;i++)
	{
		while(top>1&&(P[i]-S[top-1])*(S[top]-S[top-1])>=0)top--;
		S[++top]=P[i];
	}
	printf("%.4lf",DC(eps,10));
}