[bzoj4570]-[SCOI2016]妖怪

狂补计算几何ing


题目(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("%d",&n);
    for(register int i=0;i<n;++i)scanf("%lf%lf",&t1[i].x,&t1[i].y);
    t1[++n]=(Point){0,0};
    UpConvexHull(t1,n,t2);
    for(register int i=0;i<m;++i){solve(i);}
    printf("%.4lf",ans);
    return 0;
}

我这代码常数真的很大……

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注