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));
}