C++ 解法, 执行用时: 77ms, 内存消耗: 576K, 提交时间: 2021-11-12 22:36:32

#include<bits/stdc++.h>
using namespace std;
#define db double

struct P{
    db x, y;
    P(db x=0, db y=0):x(x),y(y){}
    P operator-(const P&u)const{
        return P(x-u.x, y-u.y);
    }
    db len2()const{
        return x*x+y*y;
    }
    db len()const{
        return sqrt(len2());
    }
    void print()const{
        cout<<x<<' '<<y<<'\n';
    }
};

P s, t, p, q;
db a, b;

db dis(P p, P q){
    return min({(p-q).len(), (p-s).len()+(q-t).len(), (p-t).len()+(q-s).len()});
}

P get_far(P p, int op){
    db t;
    if(op==0||op==2){
        if(op==0) t = 0;
        else t = b;
        db l = 0, r = a;
        for(int _ = 0; _<60; _++){
            db lm = (2*l+r)/3, rm = (l+2*r)/3;
            P pl(lm, t), pr(rm, t);
            if(dis(pl, p)<dis(pr, p)) l = lm;
            else r = rm;
        }
        return P(l, t);
    }else{
        if(op==3) t = 0;
        else t = a;
        db l = 0, r = b;
        for(int _ = 0; _<60; _++){
            db lm = (2*l+r)/3, rm = (l+2*r)/3;
            P pl(t, lm), pr(t, rm);
            if(dis(pl, p)<dis(pr, p)) l = lm;
            else r = rm;
        }
        return P(t, l);
    }
}
P d[4];
void solve(){
    cin>>a>>b>>s.x>>s.y>>t.x>>t.y;
    d[0] = P(0, 0), d[1] = P(0, b);
    d[2] = P(a, 0), d[3] = P(a, b);
    db mx = 0;
    P mp, mq;
    for(int i = 0; i<4; i++){    
        for(int op = 0; op<4; op++){
            q = d[i];
            p = get_far(q, op);
            if(dis(p, q)>mx){
                mx = dis(p, q);
                mp = p, mq = q;
            }
        }
    }
    mp.print(), mq.print();
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);

    cout<<fixed<<setprecision(9);

    int tt; cin>>tt;
    for(int kase = 1; kase<=tt; kase++){
        cout<<"Case #"<<kase<<": \n";
        solve();
    }

    return 0;
}

C++14(g++5.4) 解法, 执行用时: 176ms, 内存消耗: 488K, 提交时间: 2020-02-20 04:24:18

#include <cstdio>
#include <cmath>
#include <algorithm>

#define rep(i_, s_, t_) for (int i_ = (s_); i_ <= (t_); ++i_)

inline double dis(double ax, double ay, double bx, double by) {
    ax -= bx;
    ay -= by;
    return sqrt(ax * ax + ay * ay);
}

double ans, ans1x, ans1y;
int a, b, px, py, qx, qy, tx, ty, ans2x, ans2y;

inline double calc(double x, double y) {
    return std::min(
        dis(x, y, tx, ty), std::min(
            dis(x, y, px, py) + dis(qx, qy, tx, ty),
            dis(x, y, qx, qy) + dis(px, py, tx, ty)
        )
    );
}


template <int wy>
inline void sub(double x, double y) {
#define f(d) (wy ? calc(x, y + d) : calc(x + d, y))
    static const double eps = 1e-10;
    double l = 0, r = wy ? b : a;
    while (r - l > eps) {
        double v = (r - l) / 3;
        double u = l + v;
        v += u;
        if (f(u) > f(v))
            r = v;
        else
            l = u;
    }
    r = f(l);
    if (r > ans) {
        ans = r;
        (wy ? y : x) += l;
        ans1x = x;
        ans1y = y;
        ans2x = tx;
        ans2y = ty;
    }
}

inline void solve(double x, double y) {
    tx = x;
    ty = y;
    sub<0>(0, 0);
    sub<1>(0, 0);
    sub<0>(0, b);
    sub<1>(a, 0);
}

int main(){
    int T;
    scanf("%d", &T);
    rep (ks, 1, T) {
        scanf("%d%d%d%d%d%d", &a, &b, &px, &py, &qx, &qy);
        ans = 0;
        solve(0, 0);
        solve(a, 0);
        solve(0, b);
        solve(a, b);
        printf("Case #%d:\n%.8f %.8f\n%.8f %.8f\n", ks, ans1x, ans1y, (double)ans2x, (double)ans2y);
    }
}