BZOJ4570:[SCOI2016]妖怪——题解
https://www.lydsy.com/JudgeOnline/problem.php?id=4570
邱老师是妖怪爱好者,他有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只妖怪在该环境下最强战斗力最低。
对于每个妖怪当点,那么就相当于是找一个斜率,使得过点之后其中最外面的线的截距之和。
那么维护一个右上凸壳,我们不难发现当y=kx+b这条直线过(x0,y0)点的时候,我们所要求的答案即为y0+x0-(kx0+y0/k),是一个对勾函数,求出k的取值后分类讨论即可。
要注意特判一个点和两个点的情况。
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef double dl;
const int N=1e6+;
const int INF=1e9;
const dl eps=1e-;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct point{
dl x,y;
point(dl xx=,dl yy=){x=xx;y=yy;}
point operator -(const point &b)const{
return point(x-b.x,y-b.y);
}
dl operator *(const point &b)const{
return x*b.y-y*b.x;
}
bool operator <(const point &b)const{
return x==b.x?y<b.y:x<b.x;
}
}p[N],q[N];
int n,l,per[N];
void graham(){
sort(p+,p+n+);
for(int i=;i<=n;i++){
while(l>=&&(q[l]-q[l-])*(p[i]-q[l])>=)l--;
q[++l]=p[i];
}
}
inline dl slope(point u,point v){
if(u.x==v.x)return INF;
return (u.y-v.y)/(u.x-v.x);
}
inline dl suan(dl k1,dl k2,dl x0,dl y0){
dl maxn=-sqrt(y0/x0),tmp;
if(maxn<k1)tmp=k1*x0+y0/k1;
else if(maxn<=k2)tmp=maxn*x0+y0/maxn;
else tmp=k2*x0+y0/k2;
return y0+x0-tmp;
}
int main(){
n=read();
for(int i=;i<=n;i++)p[i].x=read(),p[i].y=read();
graham();
dl ans=INF;
if(l==){
printf("%.4lf\n",suan(-INF,INF,q[].x,q[].y));
return ;
}
if(l==){
dl k=slope(q[],q[]);
if(k>){
printf("%.4lf\n",suan(-INF,INF,q[].x,q[].y));
return ;
}
}
int L,R;
for(int i=;i<=l;i++){
int j=i+;
dl k1=slope(q[i],q[j]);
if(k1>)continue;
L=i;break;
}
for(int i=L;i<=l;i++){
int j=i+;
dl k1=slope(q[i],q[j]);
if(k1>){R=i;break;}
}
for(int i=L;i<=R;i++){
dl l1=slope(q[i],q[i+]);
dl l2=slope(q[i],q[i-]);
if(l1>)l1=-INF;
if(l2>)l2=;
ans=min(ans,suan(l1,l2,q[i].x,q[i].y));
}
printf("%.4lf\n",ans);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者:luyouqi233。 +
+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++
最新文章
- 大数据实践-数据同步篇tungsten-relicator(mysql->;mongo)
- Find All Duplicates in an Array
- yii2 查询去重
- vbox下Oracle Enterprise liunx5.4虚拟机安装10G RAC实验(三)
- Html模板
- iOS经典面试题
- Bootstrap 模态框插件
- (转)Learning to Rank for IR的评价指标—MAP,NDCG,MRR
- Missing iOS Distribution signing identity问题解决
- MD5算法-爬虫学习(五)
- h5 动画页面
- [论文阅读] A Discriminative Feature Learning Approach for Deep Face Recognition (Center Loss)
- H3C系列之三层交换机系统版本升级
- linux利用命令重置大量密码
- udp服务端收发数据流程
- 通用redis命令
- 解决Python自带的json不能序列化data,datetime类型数据问题
- Spring Boot重要内容
- ubuntu 16.04 菜单栏中无网络链接的图标 无法上网 网络管理版本不兼容
- Servlet笔记9--Cookie