tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

ボルダリングのすすめ

雑談

7月になりました。今月もいろいろと頑張ります。今月の終わりごろには国際情報オリンピックがあり、日本からも高校生が4人参加予定です。皆さんの声援をお待ちしています。


本題に入ります。

概要

ボルダリングというのは壁にくっついた変なものを両手両足でつかんで上手く移動する感じの競技です。
図示するとこうなります。

http://judge.u-aizu.ac.jp/onlinejudge/IMAGE2/bouldering1.png

壁にくっついた変なものを使って移動する、というのはこんな感じになります。

http://judge.u-aizu.ac.jp/onlinejudge/IMAGE2/bouldering3.png

手と足の長さは違うので、時には上下さかさまにならないと進めないこともあります。

http://judge.u-aizu.ac.jp/onlinejudge/IMAGE2/bouldering2.png

いろいろな人の感想

  • パワーでごり押す訓練になりました！これからもプールの監視や洞窟探索で自分の力を磨いていきます。(21歳 学生)
  • 手足を短くすることによって、とても密集した4点につかまることができるようになりました。このスキルを生かし自動掃除機のメンテナンスなどに応用できるよう精進したいと思います。(26歳 技術職)
  • このトレーニングによって甲子園でも良い結果を残すことができました。甲子園では記念に特殊な形状の蟻の巣箱に土を入れて持ち帰りました。(17歳 学生)
  • ボルダリングによって培った経験を生かし、現在わが社では番犬の派遣サービスの向上に取り組んでおります。(34歳 サービス業)
  • シンプルな円を基調とした新しいデザインを考案したのですが、その塗り方に困っていました。ボルダリングによるトレーニングによって新しい塗り方を考案し、現在それにより塗り絵を製作しようと考えております。(26歳 イラストレーター)
  • 以前街中を歩いていた時、別れた彼氏に爆弾を設置されてしまいました。日々鍛えていたおかげで爆風の届かない場所への最短距離を求めることができ、無事怪我をしませんでした。大変感謝しております。(24歳 会社員)

予想される質問と答え

  • 必要なスキルは何かありますか？

足の長さ、手の長さ、胴体の長さが0から最大長まで好きな長さを取れるようにしておくと理想的です。

  • 後ちょっと手/足/胴が長ければ隣の岩に届くのに…

そのような岩の配置はないことが知られています。厳密に言うと、手/足/胴の長さが0.001変化しても移動回数/到達可能性は変わらないことが保障されています。

  • こんなのそれ用の施設がないとできないんじゃないの？

そうですね、そう思います。
例えば東京大学の御殿下記念館にもボルダリングウォールがあります。

ただし今回は誰でもできる取っておきの環境をお勧めします！！！

必要なもの

以下の方法を用いることによって、家からでも参加できます。
皆さんが持っているであろう物だけでもボルダリングはできます。

  • PC
  • 幾何ライブラリ (無くても可、あったほうがよい)

このサイトにアクセスします。
Bouldering | Aizu Online Judge

あとはこのサイトに書かれている方法に従ってください。








ということで

エイプリルフールでした。

「2つの同じ半径の円内の共通部分」と「2つの同じ半径の円内の共通部分」の距離を求めるのですが、いろいろ点を列挙してやればよいです。
ただし一方がもう一方に完全に含まれるケースに注意しましょう。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
using namespace std;
const double EPS = 1e-10;
const double INF = 1e+10;
const double PI = acos(-1);
// ライブラリ略
Pt p[32];
int bfs[32][32][32][32];
double L1,L2,L3;
vector<Pt> hb1;
vector<Pt> hb2;
inline void add(Pt a,Pt b,Pt c,Pt d){
	if(dLP(a,b,c)<L2){
		pair<Pt,Pt> tmp=pCL(c,L2,a,b);
		if((hb1[0]-c).det(hb1[1]-c)<-EPS)swap(hb1[0],hb1[1]);
		if(sAP(hb1[0]-c,hb1[1]-c,tmp.first-c)>=0)hb1.push_back(tmp.first);
		if(sAP(hb1[0]-c,hb1[1]-c,tmp.second-c)>=0)hb1.push_back(tmp.second);
	}
	pair<Pt,Pt> tmp2=pCL(a,L2,a,b);
	if((hb1[0]-a).det(hb1[1]-a)<-EPS)swap(hb1[0],hb1[1]);
	if(sAP(hb1[0]-a,hb1[1]-a,tmp2.first-a)>=0)hb1.push_back(tmp2.first);
	if(sAP(hb1[0]-a,hb1[1]-a,tmp2.second-a)>=0)hb1.push_back(tmp2.second);
	if(dLP(a,b,d)<L3){
		pair<Pt,Pt> tmp=pCL(d,L3,a,b);
		if((hb2[0]-d).det(hb2[1]-d)<-EPS)swap(hb2[0],hb2[1]);
		if(sAP(hb2[0]-d,hb2[1]-d,tmp.first-d)>=0)hb2.push_back(tmp.first);
		if(sAP(hb2[0]-d,hb2[1]-d,tmp.second-d)>=0)hb2.push_back(tmp.second);
	}
	tmp2=pCL(b,L3,a,b);
	if((hb2[0]-b).det(hb2[1]-b)<-EPS)swap(hb2[0],hb2[1]);
	if(sAP(hb2[0]-b,hb2[1]-b,tmp2.first-b)>=0)hb2.push_back(tmp2.first);
	if(sAP(hb2[0]-b,hb2[1]-b,tmp2.second-b)>=0)hb2.push_back(tmp2.second);
}
bool debug;
inline int check(Pt a,Pt b,Pt c,Pt d){
	if((b-a).ABS()>L2*2)return 0;
	if((d-c).ABS()>L3*2)return 0;
	hb1.clear();
	hb2.clear();
	pair<Pt,Pt> T1=pCC(a,L2,b,L2);
	pair<Pt,Pt> T2=pCC(c,L3,d,L3);
	if((T1.first-c).ABS()<L3&&(T1.first-d).ABS()<L3)return 1;
	if((T2.first-a).ABS()<L2&&(T2.first-b).ABS()<L2)return 1;
	hb1.push_back(T1.first);
	hb1.push_back(T1.second);
	hb2.push_back(T2.first);
	hb2.push_back(T2.second);
	add(a,c,b,d);
	add(a,d,b,c);
	add(b,c,a,d);
	add(b,d,a,c);
	for(int i=0;i<hb1.size();i++)for(int j=0;j<hb2.size();j++){
		if((hb1[i]-hb2[j]).ABS()<L1){
		//	if(debug)printf("%f %f %f %f\n",hb1[i].x,hb1[i].y,hb2[j].x,hb2[j].y);
			return 1;
		}
	}
	return 0;
}
int main(){
	int a;
	scanf("%d",&a);
	scanf("%lf%lf%lf",&L1,&L2,&L3);
	L1-=1e-6;
	L2-=1e-6;
	L3-=1e-6;
	for(int i=0;i<a;i++){
		double X,Y;
		scanf("%lf%lf",&X,&Y);
		p[i]=Pt(X,Y);
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++)for(int k=0;k<a;k++)for(int l=0;l<a;l++)
			bfs[i][j][k][l]=99999999;
	}
	bfs[0][1][2][3]=0;
	queue<pair<pair<int,int>,pair<int,int> > >Q;
	Q.push(make_pair(make_pair(0,1),make_pair(2,3)));
	while(Q.size()){
		int TL=Q.front().first.first;
		int TR=Q.front().first.second;
		int BL=Q.front().second.first;
		int BR=Q.front().second.second;
		int now=bfs[TL][TR][BL][BR];
		Q.pop();
		if(TL==a-1||TR==a-1||BL==a-1||BR==a-1)break;
	//	printf("%d %d %d %d: %d\n",TL,TR,BL,BR,now);
	//	debug=false;
		for(int i=0;i<a;i++){
			if(TL==i||TR==i||BL==i||BR==i)continue;
			if(bfs[min(i,TR)][max(i,TR)][BL][BR]>9999999){
				if(check(p[i],p[TR],p[BL],p[BR])){
					bfs[min(i,TR)][max(i,TR)][BL][BR]=now+1;
					Q.push(make_pair(make_pair(min(i,TR),max(i,TR)),make_pair(BL,BR)));
				}
			}
			if(bfs[min(i,TL)][max(i,TL)][BL][BR]>9999999){
	//			if(TL==4&&i==5&&BL==2&&BR==3)debug=true;
				if(check(p[TL],p[i],p[BL],p[BR])){
					bfs[min(i,TL)][max(i,TL)][BL][BR]=now+1;
					Q.push(make_pair(make_pair(min(TL,i),max(TL,i)),make_pair(BL,BR)));
				}
			}
	//		debug=false;
			if(bfs[TL][TR][min(i,BR)][max(i,BR)]>9999999){
				if(check(p[TL],p[TR],p[i],p[BR])){
					bfs[TL][TR][min(i,BR)][max(i,BR)]=now+1;
					Q.push(make_pair(make_pair(TL,TR),make_pair(min(i,BR),max(i,BR))));
				}
			}
			if(bfs[TL][TR][min(i,BL)][max(i,BL)]>9999999){
				if(check(p[TL],p[TR],p[BL],p[i])){
					bfs[TL][TR][min(i,BL)][max(i,BL)]=now+1;
					Q.push(make_pair(make_pair(TL,TR),make_pair(min(i,BL),max(i,BL))));
				}
			}
		}
		
	}
	int ret=99999999;
	for(int i=0;i<a;i++)for(int j=0;j<a;j++)for(int k=0;k<a;k++){
		ret=min(ret,bfs[i][j][k][a-1]);
		ret=min(ret,bfs[i][j][a-1][k]);
		ret=min(ret,bfs[i][a-1][j][k]);
		ret=min(ret,bfs[a-1][i][j][k]);
	}
	if(ret>999999)printf("-1\n");
	else printf("%d\n",ret);
}