[TIOJ] 1254 砲打皮皮2

- 3月 07, 2018

LINK：http://tioj.infor.org/problems/1254
　　最小圓覆蓋
　　感覺學到新的東西的感覺真好~~
　　之前在交大的時候有講過greedy的這題，不過那時候的方法的複雜度很爛@@(其實那時候是要求可以有幾個點不在圓內所以不能用這個方法)，然後我就去看了網路上的解就發現有有人用爬山法唬爛(?)，第一次學到了爬山法，不過我怎麼想就是會有測資可以把它弄爛啊@@，所以就去找了正解發現是超精妙O(N)解!!
　　
　　＂隨機增量法＂，就是假設在(1~i-1)已經有個最小圓覆蓋時，i那點只會有兩種情況：1.在圓內或圓上，也就是可以跳過它(O(1) )，或者2.在圓外，然後又可以證，如果出現這種情況時，i一定在(1~i)的最小圓覆蓋的圓周上，所以就窮舉其他兩點即可(greedy找半徑最大的圓O(i^2) )，看似很爛，不過其實第2種情況發生的機率並不高，因為i個點中已經有i-1個點在圓內了，所以如果事前先random過的話，所以在圓內的機率是(i-1)/i，在圓外則是1/i，所以總體時間複雜度為(i-1)/i*O(1)+1/i*O(i^2) = O(i)為線性！
　　
　　所以是前記得先random_shuffle，高斯消去法也是......

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long ll;
#define endl '\n'
#define PB push_back
#define MT make_tuple
#define X first
#define Y second
#define ALL(v) begin(v),end(v)
#define SZ(v) (int)(v.size())
#define eps 1e-9
#define MOD 1e9+7 
#define JIZZ ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(args...){string _s = #args; replace(ALL(_s),',',' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); error(_it,args);}

bool is_debug = 0;
void error(istream_iterator<string> _it)
{
    if(is_debug) cerr << endl;
}
template<typename T,typename... Args>
void error(istream_iterator<string> it,T a, Args... args)
{
    if(is_debug)
    {
        cerr << *it << " = " << a << "   ";
        error(++it,args...);
    }
}
class circumcenter{
    public:
        inline double three(double a1,double a2,double a3,double a4,double a5,double a6,double a7,double a8,double a9)
        {
            return a1*a5*a9+a2*a6*a7+a3*a4*a8-a3*a5*a7-a6*a8*a1-a9*a2*a4;
        }
        inline pair<double,double> center(pair<double,double> a,pair<double,double> b,pair<double,double> c)
        {
            double rr = three(a.first,a.second,1,b.first,b.second,1,c.first,c.second,1);
            double x = three(a.first*a.first+a.second*a.second,a.second,1,b.first*b.first+b.second*b.second,b.second,1,c.first*c.first+c.second*c.second,c.second,1);
            double y = three(a.first,a.first*a.first+a.second*a.second,1,b.first,b.first*b.first+b.second*b.second,1,c.first,c.first*c.first+c.second*c.second,1);
            if(abs(rr) < 1e-9) return {1e9,1e9};
            return {x/rr/2,y/rr/2};
        }
        inline double dis(pair<double,double> a,pair<double,double> b)
        {
            return hypot(a.first-b.first,a.second-b.second);
        }
}c;
int n,m;
double r = 0;
pair<double,double> p[1000009],O;
int main()
{
    JIZZ;
    while(cin >> n >> m && n && m)
    {
        r = 0;
        for(int i = 0; i < m; i++) cin >> p[i].X >> p[i].Y;
        random_shuffle(p,p+m);
        O = p[0];
        for(int i = 1; i < m; i++)
            if(c.dis(O,p[i]) > r)
            {
                O = p[i];
                for(int j = 0; j < i; j++)
                    if(c.dis(O,p[j]) > r)
                    {
                        O = {(p[i].X+p[j].X)/2,(p[i].Y+p[j].Y)/2};
                        r = c.dis(p[j],O);
                        for(int k = 0; k < j; k++)
                            if(c.dis(p[k],O) > r)
                            {
                                O = c.center(p[i],p[j],p[k]);
                                r = c.dis(O,p[j]);
                            }
                    }
            }
        cout << ceil(r) << endl;
    }
}