AOJ 2238: Nurie
ブログに記事を書きます Advent Calendar 2014 - Adventarの10日目の記事です。
成し遂げました。
メインの部分の実装は、
基本的に平面走査。
・新たに分かれるときに挿入する。
・交差するときに中身を替える。
・合体するときに削除し、Union-Findで合併する。
で本質はどこに挿入する/どこを替える/どこを削除するか。
今見ているところとその直前の点のx座標との平均xlについてx=xlと各円の交点とか、その直後の点のx座標との平均xrについてx=xrと各円の交点を求めておきます。
挿入: xrのほうで該当するy座標を含む場所。(1通り)
削除: xlのほうで該当するy座標を含む場所。(1通り)
交差: それぞれどこの円上の点なのか、円の中で上半分なのか下半分なのかを考えて、その点で交差しているかどうかをひとつひとつ調べます。これが一番大変です。
あとはグラフ作って流して終わり。
double x[30]; double y[30]; double r[30]; Pt p[30]; vector<Pt> v; vector<int>now; vector<pair<double,double> > seg; int UF[1200]; int FIND(int a){ if(UF[a]<0)return a; return UF[a]=FIND(UF[a]); } void UNION(int a,int b){ a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a; } int to[1200]; int g[1200][1200]; int tg[1200][1200]; int tL[1200]; int L[1200]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<1200;i++)UF[i]=-1; for(int i=0;i<a;i++)scanf("%lf%lf%lf",x+i,y+i,r+i); for(int i=0;i<a;i++){ p[i]=Pt(x[i],y[i])*Pt(cos(1),sin(1)); } p[a]=Pt(0,0); r[a]=1000000; //a++; //for(int i=0;i<a;i++)r[i]+=EPS; for(int i=0;i<a;i++){ bool ok=true; for(int j=0;j<v.size();j++){ if((p[i]-Pt(r[i],0)-v[j]).ABS()<eps)ok=false; } if(ok)v.push_back(p[i]-Pt(r[i],0)); ok=true; for(int j=0;j<v.size();j++){ if((p[i]+Pt(r[i],0)-v[j]).ABS()<eps)ok=false; } if(ok)v.push_back(p[i]+Pt(r[i],0)); } for(int i=0;i<a;i++){ for(int j=i+1;j<a;j++){ if(iCC(p[i],r[i],p[j],r[j])==1){ pair<Pt,Pt> tmp=pCC(p[i],r[i],p[j],r[j]); bool ok=true; for(int k=0;k<v.size();k++){ if((v[k]-tmp.first).ABS()<eps)ok=false; } if(ok)v.push_back(tmp.first); ok=true; for(int k=0;k<v.size();k++){ if((v[k]-tmp.second).ABS()<eps)ok=false; } if(ok)v.push_back(tmp.second); } } } std::sort(v.begin(),v.end()); v.push_back(Pt(10000,0)); seg.push_back(make_pair(-10000,10000)); int sz=0; now.push_back(sz++); for(int i=0;i<v.size()-1;i++){ int t=1; // printf("%.12f %.12f\n",v[i].x,v[i].y); double mx=(v[i+1].x+v[i].x)/2; vector<double>tmp2; tmp2.push_back(-10000); tmp2.push_back(10000); for(int j=0;j<a;j++){ if(dLP(Pt(mx,0),Pt(mx,1),p[j])<r[j]){ t+=2; pair<Pt,Pt>sc=pCL(p[j],r[j],Pt(mx,0),Pt(mx,1)); tmp2.push_back(sc.first.y); tmp2.push_back(sc.second.y); } } std::sort(tmp2.begin(),tmp2.end()); vector<double>tmp; tmp.push_back(tmp2[0]); for(int j=1;j<tmp2.size();j++)tmp.push_back(tmp2[j]); // t=tmp.size()-1; for(int j=0;j<now.size()-1;j++){ tg[now[j]][now[j+1]]=tg[now[j+1]][now[j]]=1; } // for(int j=0;j<seg.size();j++)printf("(%.12f, %.12f) ",seg[j].first,seg[j].second);printf("\n"); if(t>now.size()){ int at=-1; for(int j=0;j<tmp2.size()-1;j++)if(tmp2[j]<v[i].y&&tmp2[j+1]>v[i].y)at=j; at--; // printf("%d\n",at); now.push_back(-1); now.push_back(-1); for(int j=now.size()-3;j>=at;j--){ now[j+2]=now[j]; } if(at%2==0)tL[sz]=1; now[at+1]=sz++; }else if(t<now.size()){ int at=-1; for(int j=0;j<now.size();j++)if(seg[j].first<v[i].y&&v[i].y<seg[j].second)at=j; // printf("%d\n",at); UNION(now[at-1],now[at+1]); for(int j=at;j<now.size()-2;j++)now[j]=now[j+2]; now.pop_back();now.pop_back(); }else{ int at=-1; for(int j=0;j<now.size();j++){ int ci=-1; int cj=-1; for(int k=0;k<a;k++)if(ABS((Pt(mx,tmp2[j])-p[k]).ABS()-r[k])<eps)ci=k; bool ui=false; bool uj=false; if(v[i].y>p[ci].y)ui=true; for(int k=0;k<a;k++)if(ABS((Pt(mx,tmp2[j+1])-p[k]).ABS()-r[k])<eps)cj=k; if(v[i].y>p[cj].y)uj=true; if(!~ci||!~cj)continue; if(ABS((v[i]-p[ci]).ABS()-r[ci])<eps&&ABS((v[i]-p[cj]).ABS()-r[cj])<eps){ if(ui&&tmp2[j]<p[ci].y)continue; if(uj&&tmp2[j+1]<p[cj].y)continue; if(!ui&&tmp2[j]>p[ci].y)continue; if(!uj&&tmp2[j+1]>p[cj].y)continue; at=j; // printf("%d\n",j); if(at%2)tL[sz]=1; now[at]=sz++; } } } seg.clear(); for(int j=0;j<tmp.size()-1;j++){ seg.push_back(make_pair(tmp[j],tmp[j+1])); } // for(int j=0;j<now.size();j++)printf("%d ",now[j]); //printf("\n"); } int n=0; for(int i=0;i<sz;i++)if(UF[i]<0)to[i]=n++; for(int i=0;i<sz;i++)to[i]=to[FIND(i)]; for(int i=0;i<sz;i++)L[to[i]]=tL[i]; for(int i=0;i<sz;i++){ for(int j=0;j<sz;j++){ if(to[i]!=to[j])g[to[i]][to[j]]|=tg[i][j]; } } //for(int i=0;i<sz;i++)printf("%d ",to[i]); //printf("\n"); sz=n; if(b>=2){ printf("%d\n",sz-1);return 0; } int S=sz*2; int T=sz*2+1; for(int i=0;i<sz;i++){ if(to[0]==i)continue; if(L[i])add_edge(S,i,1); else add_edge(i+sz,T,1); } for(int i=0;i<sz;i++)for(int j=0;j<sz;j++){ if(to[0]==i||to[0]==j)continue; if(L[i]&&g[i][j]){ add_edge(i,j+sz,1); } } //printf("%d\n",sz); //for(int i=0;i<sz;i++){ // for(int j=0;j<sz;j++){ // printf("%d ",g[i][j]); // } // printf("\n"); // } printf("%d\n",sz-1-max_flow(S,T)); }