(Codechef) WiFi Expenses [最小包覆圓(?)]

https://www.codechef.com/problems/INF16L

不太營養的解：

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cassert>
#include <iomanip>
#include <bitset>
using namespace std;

typedef long long      LL;
typedef double    ld;
typedef pair<int,int>  pii;
typedef pair<LL,LL>    pLL;
typedef vector<int>    vint;
typedef vector<LL>     vLL;
typedef vector<pii>    vpii;
typedef vector<pLL>    vpLL;

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL);
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL,(f)*1LL);

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

#define IOS ios::sync_with_stdio(0); cin.tie(0);

int myRnd() {
    return abs(  ((rand()<<15) ^ rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)^rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 51 + 6;

int a[N];

typedef pair<ld,ld> pdd;

const ld eps = 1e-9;

pdd p[N];

const int C = 36;

int n;

bool check(ld cx,ld cy,ld r)
{
    int ans = 0;
    REP1(i,n)
    {
        if (pow(cx-p[i].F,2) + pow(cy-p[i].S,2) + eps <= r*r) ans++;
        else ;
    }
    return (ans >= n-4);
}

ld get_ans(ld cx,ld cy)
{
    ld l=0,r=35000;
    int cnt = C;
    while (cnt--)
    {
        ld mid=(l+r)/2;
        if (check(cx,cy,mid)) r=mid;
        else l=mid;
    }
    //cout<<"cx = "<<cx<<" , cy = "<<cy<<" , r = "<<r<<endl;
    return r;
}

const pdd GG = {123456789,987654321};

pdd get_ans_2(ld a1,ld b1,ld c1,ld a2,ld b2,ld c2)
{
    ld delta = a1*b2-a2*b1;
    ld deltax = c1*b2-c2*b1;
    ld deltay = a1*c2-c1*a2;
    if (abs(delta) <= eps) return GG;
    else return make_pair(deltax/delta,deltay/delta);
}

int main () {
    IOS;
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        REP1(i,n)
        {
            cin >> p[i].F >> p[i].S;
        }
        ld ans=1e18,ansx=0,ansy=0;
        for (int i=1;n>=i;++i)
        {
            for (int j=i+1;n>=j;++j)
            {
                ld nowx = p[i].F + p[j].F,nowy = p[i].S + p[j].S;
                nowx/=2;
                nowy/=2;
                if (get_ans(nowx,nowy) < ans)
                {
                    ans = get_ans(nowx,nowy);
                    ansx=nowx;
                    ansy=nowy;
                }
            }
        }
        for (int i=1;n>=i;++i)
        {
            for (int j=i+1;n>=j;++j)
            {
                for (int k=j+1;n>=k;++k)
                {
                    int nowi=i,nowj=j;
                    ld cx1=(p[nowi].F + p[nowj].F)/2,cy1=(p[nowi].S + p[nowj].S)/2;
                    ld a1=p[nowi].F - p[nowj].F, b1=p[nowi].S - p[nowj].S;
                    ld c1=a1*cx1 + b1*cy1;
                    nowi=i,nowj=k;
                    cx1=(p[nowi].F + p[nowj].F)/2,cy1=(p[nowi].S + p[nowj].S)/2;
                    ld a2=p[nowi].F - p[nowj].F, b2=p[nowi].S - p[nowj].S;
                    ld c2=a2*cx1 + b2*cy1;
                    pdd ret = (get_ans_2(a1,b1,c1,a2,b2,c2));
                    if (ret == GG) continue;
                    ld x=ret.F,y=ret.S;
                    if (get_ans(x,y) < ans)
                    {
                        ans = get_ans(x,y);
                        ansx=x;
                        ansy=y;
                    }
                }
            }
        }
        cout << fixed << setprecision(12) << ansx <<' '<<ansy<<' '<<ans<<endl;
    }
}