2018.10.15 bzoj4570: [Scoi2016]妖怪(凸包)
程序员文章站
2022-04-01 15:51:22
...
传送门
不得不说这题有点东西啊。
看到题第一眼二分,用二次函数求范围来进行,20分滚粗了233.
于是开始思考正解。
发现可以把每只怪物的二元组属性看成二维坐标。
这时对于一只怪物,一种环境相当于是一条过了点的直线,贡献就是在横纵坐标的截距之和。
观察之后很容易发现答案只跟所有点的右上凸壳有关系。
于是我们维护所有点的上凸壳。
然后依次找每个点对答案的贡献就行了。
代码:
#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;
}