题目（BZOJ）
题目（洛谷）
这题蛮卡常的......毕竟 $$n <= 10^6$$
来说说这题吧~
首先，我们可以用斜率 $$k$$ 来代替题目中的二元组 $$(a,b)$$，然后就可以计算啦.
我们不难发现，每个妖怪的最强战斗力值一定是过其直线的横截距与纵截距之和，我们的目的是让这个和最小. 同时也能发现，对答案有贡献的点一定在上凸壳上.
对于一个点 $$(x_i,y_i)$$，经过其直线的斜率为 $$k$$，那么这条直线方程为 $$y = kx + y_i - k x_i$$ ，那么其横截距为 $$\frac{k x_i - y_i}{k}$$，纵截距为 $$y_i - k x_i$$ .
可以发现对于一个点，经过该点的直线会在某个范围内，并且我们可以在这个范围内进行二分查找.
设二分查找的 $$mid$$ 为当前点最小的最强战斗力值(即当前点最小横纵截距之和)，则
$$mid = \frac{kx_i - y_i}{k} + y_i - kx_i$$
将 $$k$$ 反解出来，得
$$k = (x_i + y_i - mid)$$ ± $$\frac{\sqrt{(x_i + y_i - mid)^2 - 4 x_i y_i}}{2 x_i}$$
注意到我们解出来的 $$k$$ 有两个，只要其中一个 $$k$$ 在该范围内即可. 剩下的就是普通的二分了.
#include <bits/stdc++.h>
#define eps 1e-7
#define N 1000005
using namespace std;
int n,m;
const double INF=200000000.0;
double ans=200000000.0;
struct Point{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
}t1[N],t2[N];
typedef Point Vector;
inline Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
inline Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}
inline Vector operator * (Vector A,double b){return Vector(A.x*b,A.y*b);}
inline Vector operator / (Vector A,double b){return Vector(A.x/b,A.y/b);}
inline bool operator < (const Point &a,const Point &b){return a.x>b.x||(a.x==b.x&&a.y>b.y);}
inline int dcmp(double x){if(fabs(x)<eps)return 0;else return x<0?-1:1;}
inline bool operator == (const Point &a,const Point &b){return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;}
inline double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}
inline double Length(Vector A){return sqrt(Dot(A,A));}
inline double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}
inline double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
inline double Area2(Point A,Point B,Point C){return Cross(B-A,C-A);}
inline Vector Rotate(Vector A,double rad){return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}
inline Vector Normal(Vector A){double L=Length(A);return Vector(-A.y/L,A.x/L);}
inline void UpConvexHull(Point *p,int n,Point *ch){
sort(p,p+n);
for(int i=0;i<n;++i){
while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)--m;
ch[m++]=p[i];
}
if(n>1)m--;
}
inline double K(int i,int j){return (t2[i].y-t2[j].y)/(t2[i].x-t2[j].x);}
inline void solve(int i){
double L,R,mid,ret=INF,tmp1=t2[i].x+t2[i].y;
double l,r;
L=0,R=INF;
if(i-1==-1)l=-INF;else l=K(i,i-1);
if(i+1==m)r=0;else r=K(i,i+1);
if(fabs(r-l)<=eps)return;
while(R-L>=eps){
mid=(L+R)/2;
double nowk1=((tmp1-mid)+(sqrt((tmp1-mid)*(tmp1-mid)-4*t2[i].x*t2[i].y)))/(2.0*t2[i].x);
double nowk2=((tmp1-mid)-(sqrt((tmp1-mid)*(tmp1-mid)-4*t2[i].x*t2[i].y)))/(2.0*t2[i].x);
if(((nowk1>=l&&nowk1<=r)||(nowk2>=l&&nowk2<=r))&&mid<ret)ret=mid,R=mid;
else L=mid;
}
ans=min(ans,ret);
}
int main(){
scanf(
for(register int i=0;i<n;++i)scanf(
t1[++n]=(Point){0,0};
UpConvexHull(t1,n,t2);
for(register int i=0;i<m;++i){solve(i);}
printf(
return 0;
}
我这代码常数真的很大......
Comments NOTHING