2016年2月20日 星期六

[HackerRank Week11]Two Array Problem

這題目不好找,附上題目連結

這題可以用分併樹 ($split-merge\ tree$) 來解決大部分的操作

搭配反轉的懶標記,操作1、2、3就解決了
把操作4的每個座標取出來也不是問題

現在問題來了
要怎麼求一群點的最小包圓?

我們可以考慮一個點一個點慢慢加入並維護最小包圓

說明:
$p_{i}$為第$i$個點
$f(i)$為$\{p_{1},p_{2},...,p_{i-1},p_{i}\}$的最小包圓

Cycle Solve1(const vector<Point>&ps)
一開始只有$p_{1}$一個點,$f(1)$的圓心$p_{1}$,半徑$0$
然後開始加入點
假設現在要把$p_{i}$加進去,先看看$p_{i}$有沒有在$f(i-1)$內或圓周上
有:甚麼都不用動
沒有:
 可以證明,$p_{i}$一定在$f(i)$的圓周上
 為了確定$f(i)$,我們必須再找找看還有哪個點也在$f(i)$的圓周上

故技重施
設$ff(j)$為$\{p_{1},p_{2},...,p_{j-1},p_{j},p_{i}\},j<i$的最小包圓
因此$f(i)=ff(i-1)$

Cycle Solve2(const vector<Point>&ps,const int i)
一開始只有$p_{1}$和$p_{i}$兩個點,$ff(1)$就是以$\overline{p_{1}p_{i}}$為直徑的圓
然後開始加入點
假設現在要把$p_{j}$加進去,先看看$p_{j}$有沒有在$ff(j-1)$內或圓周上
有:甚麼都不用動
沒有:
 可以證明,$p_{j}$一定在$ff(j)$的圓周上
 為了確定$ff(j)$,我們必須再找找看還有哪個點也在$ff(j)$的圓周上

故技重施
設$fff(k)$為$\{p_{1},p_{2},...,p_{k-1},p_{k},p_{j},p_{i}\},k<j<i$的最小包圓
因此$ff(j)=fff(j-1)$

Cycle Solve3(const vector<Point>&ps,const int j,const int i)
一開始只有$p_{j}$和$p_{i}$兩個點,$fff(0)$就是以$\overline{p_{j}p_{i}}$為直徑的圓 (因為最小包圓的圓周可能只包含兩個點,因此$fff(0)$是允許的)
然後開始加入點
假設現在要把$p_{k}$加進去,先看看$p_{k}$有沒有在$fff(k-1)$內或圓周上
有:甚麼都不用動
沒有:
 可以證明,$p_{k}$一定在$fff(k)$的圓周上
 此時可以發現$fff(k)$上已經有了$p_{k}$、$p_{j}$和$p_{i}$三點,因此$fff(k)$可以直接算出來!

可是這樣$O(N^{3})$不就超時了嗎?

別急,我們先看看對於隨機資料,它的期望執行時間如何
粗略估計一下,只考慮圓上有三個點的情況
可以發現
在計算$f(i)$時出現點在圓外的機率是$\frac{3}{i}$
在計算$ff(j)$時出現點在圓外的機率是$\frac{2}{j}$
在計算$fff(k)$時出現點在圓外的機率是$\frac{1}{k}$

令算出$N$個點的最小包圓的執行時間為$T(N)$
$T(N)=\sum_{i=3}^{N}(\frac{3}{i}\sum_{j=2}^{i-1}(\frac{2}{j}\sum_{k=1}^{j-1}(\frac{1}{k}+\frac{k-1}{k})+\frac{j-2}{j})+\frac{i-3}{i})$
$T(N)=\sum_{i=3}^{N}(\frac{3}{i}\sum_{j=2}^{i-1}(\frac{2}{j}*j+\frac{j-2}{j})+\frac{i-3}{i})$
$T(N)=\sum_{i=3}^{N}(\frac{3}{i}\sum_{j=2}^{i-1}(2+1)+\frac{i-3}{i})$
$T(N)=\sum_{i=3}^{N}(\frac{3}{i}*(3i)+\frac{i-3}{i})$
$T(N)=\sum_{i=3}^{N}(9+1)$
$T(N)=10N$
$T(N)=O(N)$

對於隨機測資期望時間複雜度竟然是$O(N)$?!

那我們將這些要算最小包圓的點$random\_shuffle$一下就好啦XD

時間複雜度:$O(N\log N+M\log N+10^{6})$

code:
#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
const double EPS=1e-9;
unsigned int Rand()
{
    static unsigned int seed=20160219;
    seed*=0xdefaced,seed+=134454;
    return seed+=seed>>20;
}
struct Node
{
    Node *ch[2];
    const int val;
    unsigned int sz;
    bool flipped;
    Node(const int _val):ch{NULL,NULL},val(_val),sz(1),flipped(false){}
    static unsigned int Sz(Node *o){return o?o->sz:0;}
    void Maintain()
    {
        assert(!flipped);
        sz=Sz(ch[0])+1+Sz(ch[1]);
    }
    void Flip(){flipped^=true,swap(ch[0],ch[1]);}
    void PutDown()
    {
        if(!flipped)return;
        for(int d=0;d<2;d++)if(ch[d])ch[d]->Flip();
        flipped=false;
    }
};
Node *Merge(Node *a,Node *b)
{
    if(!a||!b)return a?a:b;
    if(Rand()%(a->sz+b->sz)<a->sz)
    {
        a->PutDown();
        a->ch[1]=Merge(a->ch[1],b);
        a->Maintain();
        return a;
    }
    else
    {
        b->PutDown();
        b->ch[0]=Merge(a,b->ch[0]);
        b->Maintain();
        return b;
    }
}
void Split(Node *o,Node* &a,Node* &b,const int loc)
{
    if(!o){a=b=NULL;return;}
    if(loc<=(int)Node::Sz(o->ch[0]))
    {
        (b=o)->PutDown();
        Split(b->ch[0],a,b->ch[0],loc);
        b->Maintain();
    }
    else
    {
        (a=o)->PutDown();
        Split(a->ch[1],a->ch[1],b,loc-Node::Sz(o->ch[0])-1);
        a->Maintain();
    }
}
typedef long long LL;
void Extract(Node *o,vector<double>&output)
{
    if(!o)return;
    o->PutDown();
    Extract(o->ch[0],output);
    output.push_back(o->val);
    Extract(o->ch[1],output);
}
struct Point
{
    double x,y;
    Point():x(),y(){}
    Point(const double &_x,const double &_y):x(_x),y(_y){}
    bool operator<(const Point &p)const{return x!=p.x?x<p.x:y<p.y;}
    bool operator==(const Point &p)const{return x==p.x&&y==p.y;}
//    void Print()const{printf("(%.4f,%.4f)",x,y);}
};
double Sq(const double &x){return x*x;}
double Dist(const Point &a,const Point &b){return sqrt(Sq(a.x-b.x)+Sq(a.y-b.y));}
Point MidPoint(const Point &a,const Point &b){return Point(0.5*(a.x+b.x),0.5*(a.y+b.y));}
Point Solve(const double &a,const double &b,const double &c,const double &A,const double &B,const double &C)
{
    //ax+by+c=0
    //Ax+By+C=0
    //Aax+Aby+Ac=0
    //Aax+Bay+Ca=0
    //(Ab-Ba)y+(Ac-Ca)=0
    //y=(Ca-Ac)/(Ab-Ba)
    //Bax+Bby+Bc=0
    //Abx+Bby+Cb=0
    //(Ba-Ab)x+(Bc-Cb)=0
    //x=(Cb-Bc)/(Ba-Ab)
//    printf("(%.4f,%.4f,%.4f)(%.4f,%.4f,%.4f)\n",a,b,c,A,B,C);
    return Point((C*b-B*c)/(B*a-A*b),(C*a-A*c)/(A*b-B*a));
}
struct Cycle
{
    Point o;
    double r;
    Cycle(const Point &_o):o(_o),r(0.0){}
    Cycle(const Point &a,const Point &b):o(MidPoint(a,b)),r(0.5*Dist(a,b)){}
    Cycle(const Point &a,const Point &b,const Point &c)
    {
//        printf("a=");a.Print();printf("b=");b.Print();printf("c=");c.Print();puts("");
        if((a.x-b.x)*(b.y-c.y)==(b.x-c.x)*(a.y-b.y))
        {
            o=MidPoint(a,c),r=0.5*Dist(a,c);
        }
        else
        {
            //((a.y-b.y)*t1+0.5*(a.x+b.x),(b.x-a.x)*t1+0.5*(a.y+b.y))
            //((c.y-b.y)*t2+0.5*(c.x+b.x),(b.x-c.x)*t2+0.5*(c.y+b.y))
            //(a.y-b.y)*t1-(c.y-b.y)*t2+0.5*(a.x-c.x)=0
            //(b.x-a.x)*t1-(b.x-c.x)*t2+0.5*(a.y-c.y)=0
            const Point &ans=Solve(a.y-b.y,-(c.y-b.y),0.5*(a.x-c.x),b.x-a.x,-(b.x-c.x),0.5*(a.y-c.y));
//            printf("ans=(%.4f,%.4f)\n",ans.x,ans.y);
            o=Point((a.y-b.y)*ans.x+0.5*(a.x+b.x),(b.x-a.x)*ans.x+0.5*(a.y+b.y));
            r=Dist(o,a);
        }
    }
//    void Print()const{printf("(%.4f,%.4f,r=%.4f)\n",o.x,o.y,r);}
};
Cycle Solve3(const vector<Point>&ps,const int j,const int i)
{
    Cycle cycle=Cycle(ps[j],ps[i]);
    for(int k=0;k<j;k++)if(Dist(cycle.o,ps[k])>cycle.r)
    {
        vector<Point>tmp;
        tmp.push_back(ps[k]),tmp.push_back(ps[j]),tmp.push_back(ps[i]);
        sort(tmp.begin(),tmp.end());
        cycle=Cycle(tmp[0],tmp[1],tmp[2]);
    }
//    cycle.Print();
    return cycle;
}
Cycle Solve2(const vector<Point>&ps,const int i)
{
    Cycle cycle=Cycle(ps[0],ps[i]);
    for(int j=1;j<i;j++)if(Dist(cycle.o,ps[j])>cycle.r)cycle=Solve3(ps,j,i);
    return cycle;
}
Cycle Solve1(const vector<Point>&ps)
{
    const int n=ps.size();assert(n);
    Cycle cycle=Cycle(ps[0]);
    for(int i=1;i<n;i++)if(Dist(cycle.o,ps[i])>cycle.r)cycle=Solve2(ps,i);
    return cycle;
}
Node *S[2];
int N;
int main()
{
//    freopen("in.txt","r",stdin);
    int querycount;
    scanf("%d%d",&N,&querycount);
    S[0]=S[1]=NULL;
    for(int d=0;d<2;d++)for(int i=0,v;i<N;i++)scanf("%d",&v),S[d]=Merge(S[d],new Node(v));
    for(int type;querycount--;)
    {
        scanf("%d",&type);
        switch(type)
        {
            case 1:
            {
                int id,l,r;scanf("%d%d%d",&id,&l,&r),l--;
                Node *a,*b,*c;
                Split(S[id],b,c,r);
                Split(b,a,b,l);
                b->Flip();
                S[id]=Merge(a,Merge(b,c));
            }break;
            case 2:
            {
                int id,l1,r1,l2,r2;scanf("%d%d%d%d%d",&id,&l1,&r1,&l2,&r2),l1--,l2--;
                Node *a,*b,*c,*d,*e;
                Split(S[id],d,e,r2);
                Split(d,c,d,l2);
                Split(c,b,c,r1);
                Split(b,a,b,l1);
                S[id]=Merge(Merge(a,d),Merge(c,Merge(b,e)));
            }break;
            case 3:
            {
                int l,r;scanf("%d%d",&l,&r),l--;
                Node *a0,*b0,*c0,*a1,*b1,*c1;
                Split(S[0],b0,c0,r);
                Split(b0,a0,b0,l);
                Split(S[1],b1,c1,r);
                Split(b1,a1,b1,l);
                S[0]=Merge(a0,Merge(b1,c0));
                S[1]=Merge(a1,Merge(b0,c1));
            }break;
            case 4:
            {
                int l,r;scanf("%d%d",&l,&r),l--;
                Node *a0,*b0,*c0,*a1,*b1,*c1;
                Split(S[0],b0,c0,r);
                Split(b0,a0,b0,l);
                Split(S[1],b1,c1,r);
                Split(b1,a1,b1,l);
                vector<double>xs,ys;
                Extract(b0,xs),Extract(b1,ys);
                S[0]=Merge(a0,Merge(b0,c0));
                S[1]=Merge(a1,Merge(b1,c1));
                assert(xs.size()==ys.size());
                vector<Point>ps;
                for(int i=0;i<(int)xs.size();i++)ps.push_back(Point(xs[i],ys[i]));
                sort(ps.begin(),ps.end()),ps.resize(unique(ps.begin(),ps.end())-ps.begin());
                random_shuffle(ps.begin(),ps.end());//for fear of degenerating of time complexity
//                for(const Point &p:ps)printf("(%.0f,%.0f)",p.x,p.y);puts("");
                printf("%.2f\n",Solve1(ps).r);
            }break;
        }
        assert((int)S[0]->sz==N&&(int)S[1]->sz==N);
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原