题意
Problem 4570. -- [Scoi2016]妖怪4570: [Scoi2016]妖怪
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1251 Solved: 399
[Submit][Status][Discuss]Description
邱老师是妖怪爱好者，他有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只妖怪在该环境下最强战斗力最低。
Input
第一行一个n，表示有n只妖怪。接下来n行，每行两个整数atk和dnf，表示妖怪的攻击力和防御力。
1≤n≤10^6, 0＜atk,dnf≤10^8
Output
输出在最不利情况下最强妖怪的战斗力值，保留4位小数。
Sample Input
3
1 1
1 2
2 2
Sample Output
8.0000
HINT
Source
[Submit][Status][Discuss]?
HOME
Back
分析
参照Sky_miner的题解。
我们知道如果一个怪物要取到攻击力的最大值,那么一定是把防御力都转化了
所以我们可以把题目转化成这个式子
求\[\min(\max(atk + dnf + \frac{a}{b}dnf + \frac{b}{a}atk))\]
我们设\(k = -\frac{b}{a}\)
那么上式变为了\[\min(\max(atk + dnf - (\frac{1}{k}dnf + k*atk)))\]
右侧括号里是对勾函数的形式,我们由数学知识得\(k = -\sqrt{\frac{dnf}{atk}}\)时取得最值
现在我们尝试把所有怪物的属性看成点映射到二维平面
设点\((x,y)\),假设通过了一条斜率为\(k(k < 0)\)的直线
我们通过计算发现这个直线的横纵截距之和即为我们上面的计算式
而当\(k = -\sqrt{\frac{dnf}{atk}}\)横纵截距之和最小
所以问题转化成了为二维平面上的一些点确定一些平行线通过这些点使得最大的横纵截距之和最小
我们知道最大的条直线一定是通过上凸壳上的点的
所以我们枚举上凸壳上的点即可
时间复杂度\(O(n \log n)\)
代码
用operator*代替Dot，用operator/代替Cross，比较好写。
#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;
rg char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') w=-1;
ch=getchar();
}
while(isdigit(ch))
data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x){
return x=read<T>();
}
typedef long long ll;
co double eps=1e-8;
typedef struct Point {double x,y;}Vector;
Vector operator+(co Vector&a,co Vector&b) {return (Vector){a.x+b.x,a.y+b.y};}
Vector operator-(co Vector&a,co Vector&b) {return (Vector){a.x-b.x,a.y-b.y};}
double operator*(co Vector&a,co Vector&b) {return a.x*b.x+a.y*b.y;}
double operator/(co Vector&a,co Vector&b) {return a.x*b.y-a.y*b.x;}
double min_p(co Point&x) {return -sqrt(x.y/x.x);}
int dcmp(double x) {return fabs(x)<eps?0:(x<0?-1:1);}
double slope(co Point&a,co Point&b){
if(dcmp(a.x)==0&&dcmp(a.y)==0) return 1e10;
if(dcmp(b.x)==0&&dcmp(b.y)==0) return -1e10;
if(dcmp(a.x-b.x)==0) return 1e10;
return (b.y-a.y)/(b.x-a.x);
}
bool cmp(co Point&a,co Point&b) {return dcmp(a.x-b.x)==0?a.y<b.y:a.x<b.x;}
double calc(co Point&p,double k){
if(k>=0) return 1e10;
return p.x+p.y-k*p.x-p.y/k;
}
co int N=1e6+1;
Point p[N],ch[N];
int n,m;
void convex(){
ch[m=1]=p[1];
for(int i=2;i<=n;++i){
while(m>1&&dcmp((ch[m]-ch[m-1])/(p[i]-ch[m]))>=0) --m;
ch[++m]=p[i];
}
std::swap(n,m),std::swap(p,ch);
}
int main(){
// freopen(".in","r",stdin),freopen(".out","w",stdout);
read(n);
for(int i=1;i<=n;++i) read(p[i].x),read(p[i].y);
if(n==1) return printf("%.4lf\n",calc(p[1],min_p(p[1]))),0;
std::sort(p+1,p+n+1,cmp),convex();
double ans=1e10;
double k1,k2,k;
k2=slope(p[1],p[2]), k=min_p(p[1]);if(k>=k2) ans=std::min(ans,calc(p[1],k));
k1=slope(p[n-1],p[n]),k=min_p(p[n]);if(k<=k1) ans=std::min(ans,calc(p[n],k));
ans=std::min(ans,calc(p[n],k1));
for(int i=2;i<n;++i){
k=min_p(p[i]),k1=slope(p[i-1],p[i]),k2=slope(p[i],p[i+1]);
ans=std::min(ans,calc(p[i],k1));
if(dcmp(k-k1)<=0&&dcmp(k-k2)>=0) ans=std::min(ans,calc(p[i],k));
}
printf("%.4lf\n",ans);
return 0;
}
BZOJ4570 [Scoi2016]妖怪
原文：https://www.cnblogs.com/autoint/p/10529655.html
