這題可以用分併樹 ($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誤判成垃圾留言，小莫會盡快將其手動還原
注意：只有此網誌的成員可以留言。