2017多校第6场 HDU 6097 Mindis 计算几何，圆的反演

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6097

题意：有一个圆心在原点的圆，给定圆的半径，给定P、Q两点坐标（PO=QO，P、Q不在圆外），取圆上一点D，求PD+QD的最小值。

解法：圆的反演。

很不幸不总是中垂线上的点取到最小值，考虑点在圆上的极端情况。

做P点关于圆的反演点P',OPD与ODP'相似，相似比是|OP| : r。

Q点同理。

极小化PD+QD可以转化为极小化P'D+Q'D。

当P'Q'与圆有交点时，答案为两点距离，否则最优值在中垂线上取到。

时间复杂度 O(1)

也有代数做法，结论相同。

优秀的黄金分割三分应该也是可以卡过的。

分析可以看这个博客：http://blog.csdn.net/qq_34845082/article/details/77099332

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

struct FastIO

{

    static const int S = 1310720;

    int wpos;

    char wbuf[S];

    FastIO() : wpos(0) {}

    inline int xchar()

    {

        static char buf[S];

        static int len = 0, pos = 0;

        if(pos == len)

            pos = 0, len = fread(buf, 1, S, stdin);

        if(pos == len)

            exit(0);

        return buf[pos ++];

    }

    inline unsigned long long xuint()

    {

        int c = xchar();

        unsigned long long x = 0;

        while(c <= 32)

            c = xchar();

        for(; '0' <= c && c <= '9'; c = xchar())

            x = x * 10 + c - '0';

        return x;

    }

    inline long long xint()

    {

        long long s = 1;

        int c = xchar(), x = 0;

        while(c <= 32)

            c = xchar();

        if(c == '-')

            s = -1, c = xchar();

        for(; '0' <= c && c <= '9'; c = xchar())

            x = x * 10 + c - '0';

        return x * s;

    }

    inline void xstring(char *s)

    {

        int c = xchar();

        while(c <= 32)

            c = xchar();

        for(; c > 32; c = xchar())

            * s++ = c;

        *s = 0;

    }

    inline double xdouble()

    {

        bool sign = 0;

        char ch = xchar();

        double x = 0;

        while(ch <= 32)

            ch = xchar();

        if(ch == '-')

            sign = 1, ch = xchar();

        for(; '0' <= ch && ch <= '9'; ch = xchar())

            x = x * 10 + ch - '0';

        if(ch == '.')

        {

            double tmp = 1;

            ch = xchar();

            for(; ch >= '0' && ch <= '9'; ch = xchar())

                tmp /= 10.0, x += tmp * (ch - '0');

        }

        if(sign)

            x = -x;

        return x;

    }

    inline void wchar(int x)

    {

        if(wpos == S)

            fwrite(wbuf, 1, S, stdout), wpos = 0;

        wbuf[wpos ++] = x;

    }

    inline void wint(long long x)

    {

        if(x < 0)

            wchar('-'), x = -x;

        char s[24];

        int n = 0;

        while(x || !n)

            s[n ++] = '0' + x % 10, x /= 10;

        while(n--)

            wchar(s[n]);

    }

    inline void wstring(const char *s)

    {

        while(*s)

            wchar(*s++);

    }

    inline void wdouble(double x, int y = 8)

    {

        static long long mul[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000LL, 100000000000LL, 1000000000000LL, 10000000000000LL, 100000000000000LL, 1000000000000000LL, 10000000000000000LL, 100000000000000000LL};

        if(x < -1e-12)

            wchar('-'), x = -x;

        x *= mul[y];

        long long x1 = (long long) floorl(x);

        if(x - floor(x) >= 0.5)

            ++x1;

        long long x2 = x1 / mul[y], x3 = x1 - x2 * mul[y];

        wint(x2);

        if(y > 0)

        {

            wchar('.');

            for(size_t i = 1; i < y && x3 * mul[i] < mul[y]; wchar('0'), ++i);

            wint(x3);

        }

    }

    ~FastIO()

    {

        if(wpos)

            fwrite(wbuf, 1, wpos, stdout), wpos = 0;

    }

} io;

const double eps = 1e-8;

double getDis(double x, double y){

    return sqrt(x*x+y*y);

}

double r,x1,y1,x2,y2;

int main()

{

    int T = io.xint();

    while(T--)

    {

        r = io.xdouble();

        x1 = io.xdouble();

        y1 = io.xdouble();

        x2 = io.xdouble();

        y2 = io.xdouble();

        double d0 = getDis(x1, y1);

        if(fabs(d0)<=eps){//p和q和原点重合

            printf("%.8f\n", 2*r);

            continue;

        }

        double k = r*r/d0/d0;//用这个比例确定p和q的反演点

        double x3=x1*k, x4=x2*k;

        double y3=y1*k, y4=y2*k;

        double mx=(x3+x4)/2.0,my=(y3+y4)/2.0;

        double ans;

        double d = getDis(mx, my);

        if(d <= r){//判断反演点和半径的关系 如果两个反演点的中点到圆心的距离小于半径

            double dis = getDis(x3-x4,y3-y4);

            ans = dis*d0/r;

        }

        else{//其他的即是连线与圆相离时的状态 这时候的d点是p和q的反演点的连线的中垂线与圆的交点

            double kk=r/d;//其他的即是连线与圆相离时的状态 这时候的d点是p和q的反演点的连线的中垂线与圆的交点

            double smx = mx*kk, smy = my*kk;

            ans = 2*getDis(smx-x1,smy-y1);

        }

        printf("%.8f\n", ans);

    }

    return 0;

}