BZOJ 4570 妖怪

发表于 | 更新于

Link

纸张居然连二分答案都搞不对

Solution

atk+k1a+dnf+k2b≤Midatk+k_1a+dnf+k_2b\le Mid dnf−k1b≥0dnf-k_1b\ge 0 atk−k2a≥0atk-k_2a\ge 0 带了一堆变量，然后需要用整体的思想 首先atk+k1aatk+k_1a取最值的时候dnf−k1b==0dnf-k_1b==0。另一个限制也一样。 所以变成了 atk+dnf×ab+dnf+atk×ba≤Midatk+\dfrac {dnf\times a}b+dnf+\dfrac {atk\times b}a\le Mid 然后上二分答案，解不等式。。然后就T了 但是这个思维过程也是必不可少的

能往凸包上想简直太妙了

换个思路。把每个妖怪看成一个点，x0=atk,y0=dnfx_0=atk,y_0=dnf，答案可以写成x0+ay0b+y0+bx0ax_0+\dfrac {ay_0}b+y_0+\dfrac {bx_0}a。 y−y0x−x0=−ba\dfrac {y-y_0}{x-x_0}=-\dfrac ba在横纵轴的截距和！ 这样想想，显然只有在凸包上的点才有可能成为最大值，具体地说，必须在右上凸包 在右上凸包上，对于每条边，代入斜率求一下端点的值，可以保证每个点的取值都是所有点的取值中，当前斜率下的最大值。 然而还可能有些点，把直线的斜率转一转一样是全局最大值，但可以变得更小。根据均值不等式，应该取−y0x0-\sqrt {\dfrac{y_0}{x_0}}。如果这个斜率的直线与凸包是相切的，那么也可以拿来更新答案。

Tips

多个变量变来变去试试整体代入(才几个月没上课就连数学的基本方法都不会了) 改用基于水平序的扫描法求凸包！比 好写多了。尤其是求半个凸壳的情况就更方便了。 猜一猜式子的含义，搞一搞数形结合。

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;
}