BZOJ 4570 妖怪

Link

纸张居然连二分答案都搞不对 # Solution \(atk+k_1a+dnf+k_2b\le Mid\) \(dnf-k_1b\ge 0\) \(atk-k_2a\ge 0\) 带了一堆变量,然后需要用整体的思想 首先\(atk+k_1a\)取最值的时候\(dnf-k_1b==0\)。另一个限制也一样。 所以变成了 \(atk+\dfrac {dnf\times a}b+dnf+\dfrac {atk\times b}a\le Mid\) 然后上二分答案,解不等式。。然后就T了 但是这个思维过程也是必不可少的

能往凸包上想简直太妙了

换个思路。把每个妖怪看成一个点,\(x_0=atk,y_0=dnf\),答案可以写成\(x_0+\dfrac {ay_0}b+y_0+\dfrac {bx_0}a\)\(\dfrac {y-y_0}{x-x_0}=-\dfrac ba\)在横纵轴的截距和! 这样想想,显然只有在凸包上的点才有可能成为最大值,具体地说,必须在右上凸包 在右上凸包上,对于每条边,代入斜率求一下端点的值,可以保证每个点的取值都是所有点的取值中,当前斜率下的最大值。 然而还可能有些点,把直线的斜率转一转一样是全局最大值,但可以变得更小。根据均值不等式,应该取\(-\sqrt {\dfrac{y_0}{x_0}}\)。如果这个斜率的直线与凸包是相切的,那么也可以拿来更新答案。 # Tips 多个变量变来变去试试整体代入(才几个月没上课就连数学的基本方法都不会了) 改用基于水平序的扫描法求凸包!比\(\rm Graham\)好写多了。尤其是求半个凸壳的情况就更方便了。 猜一猜式子的含义,搞一搞数形结合。 # Code

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include "lucida"
using std::sort;
using std::swap;
using std::unique;
using std::reverse;
const int MAXN=1e6+11;
const double inf=1e100,eps=1e-7;
int fcmp(const double &x) {
return -eps<x && x<eps?0:(x<0?-1:1);
}
struct point {
double x,y;
point() {}
point(double x,double y):x(x),y(y) {}
double slope() const {
return fcmp(x)?y/x:inf;
}
double len() const {
return sqrt(x*x+y*y);
}
friend point operator +(const point &a,const point &b) {
return point(a.x+b.x,a.y+b.y);
}
friend point operator -(const point &a,const point &b) {
return point(a.x-b.x,a.y-b.y);
}
bool operator < (const point &a) const {
return x!=a.x?x<a.x:y>a.y;
}
bool operator ==(const point &a) const {
return x==a.x && y==a.y;
}
};
typedef point vector;
double outer(const vector &a,const vector &b) {
return a.x*b.y-a.y*b.x;
}
double Calc(point p,double k) {
return p.x+p.y-p.x*k-p.y/k;
}
int main() {
// freopen("input","r",stdin);
static point p[MAXN],stack[MAXN];
static double pk[MAXN];
int n;is>>n;
for(int i=1;i<=n;++i) {
is>>p[i].x>>p[i].y;
}
sort(p+1,p+1+n);
n=unique(p+1,p+1+n)-p-1;
int top=0;
for(int i=n;i;--i) {
while(top>=2 && outer(stack[top]-stack[top-1],p[i]-stack[top])<0) {
top--;
}
stack[++top]=p[i];
}
n=0;
for(int i=1;i<=top;++i) {
p[++n]=stack[i];
if((stack[i+1]-stack[i]).slope()>=0) {
break;
}
}
reverse(p+1,p+1+n);
for(int i=2;i<=n;++i) {
pk[i]=(p[i]-p[i-1]).slope();
}
pk[1]=-inf;pk[n+1]=inf;
double Ans=inf;
for(int i=1;i<=n;++i) {
double mik=-sqrt(p[i].y/p[i].x);
if(fcmp(pk[i]-mik)>=0 && fcmp(mik-pk[i+1])>=0) {
chkmn(Ans,Calc(p[i],mik));
}
if(pk[i]!=inf && pk[i]!=-inf) {
chkmn(Ans,Calc(p[i],pk[i]));
}
}
os.precision(4);
os<<Ans<<'\n';
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利