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

2018.10.15 bzoj4570: [Scoi2016]妖怪(凸包)

程序员文章站 2022-04-01 15:51:22
...

传送门
不得不说这题有点东西啊。


看到题第一眼二分,用二次函数求范围来进行checkcheck,20分滚粗了233.
于是开始思考正解。
发现可以把每只怪物的二元组属性看成二维坐标。
这时对于一只怪物(x,y)(x,y),一种环境相当于是一条过了点(x,y)(x,y)的直线,贡献就是在横纵坐标的截距之和。
观察之后很容易发现答案只跟所有点的右上凸壳有关系。
于是我们维护所有点的上凸壳。
然后依次找每个点对答案的贡献就行了。
代码:

#include<bits/stdc++.h>
#define db double
#define N 1000005
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
int n,q[N],top=0;
struct pot{db x,y;}p[N];
const double inf=2e9,eps=1e-10;
inline bool cmp(const pot&a,const pot&b){return a.x==b.x?a.y<b.y:a.x<b.x;}
inline double calc(const pot&a,double k){return a.x+a.y+a.x*k+a.y/k;}
inline double slope(const pot&a,const pot&b){return (a.y-b.y)/(a.x-b.x);}
inline pot operator-(const pot&a,const pot&b){return (pot){a.x-b.x,a.y-b.y};}
inline double operator^(const pot&a,const pot&b){return a.x*b.y-a.y*b.x;}
inline double solve(){
	double ret=inf,l=-inf,r,k;
	for(int i=1;i<=top;++i){
		r=l,l=i==top?-eps:slope(p[q[i]],p[q[i+1]]),k=-sqrt(p[q[i]].y/p[q[i]].x);
		if(l<=k&&k<=r)ret=min(ret,calc(p[q[i]],-k));
		else ret=min(ret,calc(p[q[i]],-l)),ret=min(ret,calc(p[q[i]],-r));
	}
	return ret;
}
int main(){
	n=read();
	for(int i=1;i<=n;++i)p[i].x=read(),p[i].y=read();
	sort(p+1,p+n+1,cmp);
	for(int i=n;i;--i){
		while(top>2&&((p[i]-p[q[top-1]])^(p[q[top]]-p[q[top-1]]))>=0)--top;
		q[++top]=i;
	}
	while(top>1&&p[q[top]].y<=p[q[top-1]].y)--top;
	printf("%.4lf",solve());
	return 0;
}
相关标签: 计算几何