欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[Luogu P3291] [BZOJ 3570] [SCOI2016]妖怪

程序员文章站 2024-01-31 08:13:40
...

洛谷传送门

BZOJ传送门

题目描述

邱老师是妖怪爱好者,他有nn只妖怪,每只妖怪有攻击力atk和防御力dnf两种属性。邱老师立志成为妖怪大师,于是他从真新镇出发,踏上未知的旅途,见识不同的风景。

环境对妖怪的战斗力有很大影响,在某种环境中,妖怪可以降低自己kak*a点攻击力,提升kbk*b点防御力或者,提升自己kak*a点攻击力,降低kbk*b点防御力,aabb属于正实数,kk为任意实数,但是atk和dnf必须始终非负。

妖怪在环境(a,b)(a,b)中的战斗力为妖怪在该种环境中能达到的最大攻击力和最大防御力之和。strength(a,b)=max(atk(a,b))+max(dnf(a,b))strength(a,b)=max(atk(a,b))+max(dnf(a,b))环境由aabb两个参数定义,aabb的含义见前文描述。

比如当前环境a=3a=3b=2b=2,那么攻击力为66,防御力为22的妖怪,能达到的最大攻击力为99,最大防御力为66。所以该妖怪在a=3a=3b=2b=2的环境下战斗力为1515

因此,在不同的环境,战斗力最强的妖怪可能发生变化。

作为一名优秀的妖怪训练师,邱老师想发掘每一只妖怪的最大潜力,他想知道在最为不利的情况下,他的nn只妖怪能够达到的最强战斗力值,即存在一组正实数(a,b)(a,b)使得nn只妖怪在该环境下最强战斗力最低。

输入输出格式

输入格式:

第一行一个nn,表示有nn只妖怪。

接下来nn行,每行两个整数atk和dnf,表示妖怪的攻击力和防御力。1n106,0atk,dnf1081\le n\le 10^6, 0<atk, dnf\le 10^8

输出格式:

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

输入输出样例

输入样例#1:

3
1 1
1 2
2 2

输出样例#1:

8.0000

解题分析

题目就是要我们求下面这个式子:
min(maxi=1n(x+y+bax+aby)) min(max_{i=1}^{n}(x+y+\frac{b}{a}x+\frac{a}{b}y))
k=bak=\frac{b}{a}, 那么后面那个式子就变成了x+y+kx+ykx+y+kx+\frac{y}{k}

这是个啥玩意呢? 画出平面直角坐标系可以发现这玩意就是斜率为k-k, 经过点(x,y)(x,y)的直线在xxyy轴上的截距之和。

然后发现可能成为最大值的点一定在一个上凸包上, 搞一搞就好。

由均值不等式可得这个函数的最小值在k=yxk=\sqrt \frac{y}{x}处取到, 这个点成为最大值的区间就是相邻两条线段的斜率之间的部分, 判一判是不是在这个区间内就好了。

注意右上凸包两端的点的横纵坐标分别加上EPS, 避免出现nan的情况。

代码如下:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <iostream>
#include <algorithm>
#define R register
#define IN inline
#define W while
#define db long double
#define MX 1000050
#define EPS 1e-8
template <class T> IN T max(T a, T b) {return a > b ? a : b;}
template <class T> IN T min(T a, T b) {return a < b ? a : b;}
int n, cnum;
int conv[MX];
struct Point {db x, y;}dat[MX];
IN Point operator + (const Point &x, const Point &y) {return {x.x + y.x, x.y + y.y};}
IN Point operator - (const Point &x, const Point &y) {return {x.x - y.x, x.y - y.y};}
IN db operator * (const Point &x, const Point &y) {return x.x * y.y - x.y * y.x;}
IN bool operator < (const Point &x, const Point &y) {return x.x == y.x ? x.y > y.y : x.x < y.x;}
IN db Getk(const Point &x) {return x.y / x.x;}
IN void Getconv()
{
	std::sort(dat + 1, dat + 1 + n);
	for (R int i = 1; i <= n; ++i)
	{
		W (cnum >= 2 && (dat[conv[cnum]] - dat[conv[cnum - 1]]) * (dat[i] - dat[conv[cnum - 1]]) >= 0) --cnum;
		conv[++cnum] = i;
	}
}
int main(void)
{
	db mxx = 0, mxy = 0, ratl, ratr, best;
	scanf("%d", &n);
	for (R int i = 1; i <= n; ++i)
	{
		scanf("%Lf%Lf", &dat[i].x, &dat[i].y);
		mxx = max(mxx, dat[i].x), mxy = max(mxy, dat[i].y);
	}
	dat[++n] = {0, mxy}, dat[++n] = {mxx, 0};
	Getconv(); db ans = 1e18;
	dat[conv[cnum]].x += EPS;
	dat[conv[1]].y += EPS;
	for (R int i = 2; i < cnum; ++i)
	{
		ratl = -Getk(dat[conv[i]] - dat[conv[i - 1]]);
		ratr = -Getk(dat[conv[i + 1]] - dat[conv[i]]);
		ans = min(ans, dat[conv[i]].x + dat[conv[i]].y + ratl * dat[conv[i]].x + dat[conv[i]].y / ratl);
		ans = min(ans, dat[conv[i]].x + dat[conv[i]].y + ratr * dat[conv[i]].x + dat[conv[i]].y / ratr);
		best = std::sqrt(dat[conv[i]].y / dat[conv[i]].x);
		if (best >= ratl && best <= ratr) ans = min(ans, dat[conv[i]].x + dat[conv[i]].y + best * dat[conv[i]].x + dat[conv[i]].y / best);
	}
	printf("%.4Lf", ans);
}
相关标签: 计算几何 数学