BZOJ 4570: [Scoi2016]妖怪

二次联通门 : BZOJ 4570: [Scoi2016]妖怪

二次联通门 : luogu P3291 [SCOI2016]妖怪

LibreOJ : LibreOJ  #2015. 「SCOI2016」妖怪

/*

    BZOJ 4570: [Scoi2016]妖怪

    凸包

    我果然还是naive

    看见这题就想二分

    结果惨挂

    做了凸包后就想三分

    又挂了。。

    完美落入了每个坑。。果然还是自己太菜

    对于每个妖怪，其在(a,b)时的最大战力为过当前点斜率为(-b/a)的直线的截距之和

    最大的战力就是最外面的那条直线

    对n个点做一个上凸包

    最大值一定在凸包的右上部分(自行脑补)

    那么这些点的斜率都有着一个范围ki-1<ki<ki+1

    那么战力就变为了一个双钩函数

    讨论求最值即可

*/

#include <algorithm>

#include <iostream>

#include <cstdio>

#include <cmath>

void read (long long &now)

{

    register char word = getchar ();

    int temp = ;

    for (now = ; !isdigit (word); word = getchar ())

        if (word == '-')

            temp = ;

    for (; isdigit (word); now = now *  + word - '', word = getchar ());

    if (temp)

        now = -now;

}

#define INF 1e9

struct Point

{

    long long x, y;

    Point (long long __x, long long __y) : x (__x), y (__y) {}

    Point () {}

    bool operator < (const Point &now) const

    {

        return this->x == now.x ? this->y < now.y : this->x < now.x;

    }

    Point operator - (const Point &now) const

    {

        return Point (this->x - now.x, this->y - now.y);

    }

};

inline long long Cross (const Point &A, const Point &B)

{

    return A.x * B.y - A.y * B.x;

}

#define Max 1000250

inline double Calculate (const Point &now, const double &k)

{

    return k >=  ? INF : (double) now.x + now.y + - k * now.x - now.y / k;

}

inline double Get_point_k (const Point &now)

{

    return -sqrt ((double) now.y / now.x);

}

inline double Get_line_k (const Point &A, const Point &B)

{

    return (A.x ^ B.x) ? ((double)(A.y - B.y) / (double) (A.x - B.x)) : INF;

}

int Get_convex_Hull (Point *point, int N, Point *Stack)

{

    std :: sort (point + , point + N + );

    register int top = ;

    for (int i = ; i <= N; ++ i)

    {

        for (; top >  && Cross (Stack[top] - Stack[top - ], point[i] - Stack[top - ]) >= ; -- top);

        Stack[++ top] = point[i];

    }

    return top;

}

Point yukari[Max], Stack[Max];

int main (int argc, char *argv[])

{

    register int i;

    int N;

    scanf ("%d", &N);

    for (i = ; i <= N; ++ i)

        read (yukari[i].x), read (yukari[i].y);

    int M = Get_convex_Hull (yukari, N, Stack);

    if (M < )

    {

        printf ("%.4lf", Calculate (Stack[], Get_point_k (Stack[])));

        return ;

    }

    double k, _k, __k, Answer = INF;

    k = Get_point_k (Stack[]);

    __k = Get_line_k (Stack[], Stack[]);

    if (k >= __k)

        Answer = std :: min (Answer, Calculate (Stack[], k));

    k = Get_point_k (Stack[M]);

    _k = Get_line_k (Stack[M - ], Stack[M]);

    if (k <= _k)

        Answer = std :: min (Answer, Calculate (Stack[M], k));

    Answer = std :: min (Answer, Calculate (Stack[M], _k));

    for (i = ; i < M; ++ i)

    {

        _k = Get_line_k (Stack[i - ], Stack[i]);

        __k = Get_line_k (Stack[i], Stack[i + ]);

        k = Get_point_k (Stack[i]);

        Answer = std :: min (Answer, Calculate (Stack[i], _k));

        if (k <= _k && k >= __k)

            Answer = std :: min (Answer, Calculate (Stack[i], k));

    }

    printf ("%.4lf", Answer);

    return ;

}