※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

1132 Circle and Points

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1132
平面上の点の座標が与えられるので一つの半径1の円で囲むことが出来る点の最大数を答える問題。

解法
回転行列の概念を使って交点を求めます。
後は交点を中心に円を描いたとき何個の点を囲めるかを確かめるだけです。
どうしようAOJの問題を573問解いたけど、残りの問題どれをみても解法を思いつかないのばっかりだ、、、


#include<stdio.h>
#include<math.h>
#include<vector>

void calc(double x1,double y1,double x2,double y2,std::vector<double>& pxs,std::vector<double>& pys){
	double len,len2,x3=x2-x1,y3=y2-y1,cos1,sin1,cos2,sin2,ansX,ansY;
	len=hypot(x3,y3);
	len2=len/2.0;
	cos1=x3/len;
	sin1=y3/len;
	sin2=sqrt(1.0-len2*len2);
	cos2=len2;
	pxs.push_back(cos2*cos1-sin1*sin2+x1);
	pys.push_back(sin2*cos1+sin1*cos2+y1);
	pxs.push_back(cos2*cos1+sin1*sin2+x1);
	pys.push_back(-sin2*cos1+sin1*cos2+y1);
	//printf("(%lf %lf %lf %lf)",cos2*cos1-sin1*sin2+x1,sin2*cos1+sin1*cos2+y1,
	//		cos2*cos1+sin1*sin2+x1,-sin2*cos1+sin1*cos2+y1);
}

void search(int n){
	double xs[301],ys[301];
	std::vector<double> pxs,pys;
	for(int i=0;i<n;i++){
		scanf("%lf %lf",&xs[i],&ys[i]);
	}
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(hypot(xs[i]-xs[j],ys[i]-ys[j])<=2.0){
				calc(xs[i],ys[i],xs[j],ys[j],pxs,pys);
			}
		}
	}
	int ans=1;
	for(unsigned int i=0;i<pxs.size();i++){
		int count=0;
		for(int j=0;j<n;j++){
			if(hypot(xs[j]-pxs[i],ys[j]-pys[i])<=1.000001)count++;
		}
		if(ans<count)ans=count;
	}
	printf("%d\n",ans);
}

int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0)break;
		search(n);
	}
}


1138 Traveling by Stagecoach

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1138
この問題は動的計画法で解きます。
まずチケット8枚、都市数30の場合を考えます。
ある都市にいるときどのチケットを使ってるかを考えます。
そうすると状態数はチケットの使用組み合わせ256通り*今いる都市30通り=7680個の点を持つグラフとなりこのグラフ上を移動する問題に翻訳できます。
このグラフに対して動的計画法を適用すれば解けます。
calc関数で動的計画法を実施します。
スタート地点のタイムは0です。
calc関数の外側のfor文一週目ではチケットを一枚も使ってない点だけを取り上げ動的計画法を適用します。
2週目ではチケットを一枚使った状態の点だけを取り上げ動的計画法を適用します。
3週目では2枚でこれを繰り返します。
最終的にループが終われば計算完了です。
ゴール都市でのタイムを最後のループで調べます。
この手法は泥臭い工夫ですが驚くほど効果があり、実行速度5位という良好な速度を叩き出しましたが僅差で一位を抜くことはできませんでした。
別の手法ですが、高速化の知恵を振りかけたダイクストラで攻略すれば1位を余裕で抜きされる可能性は高いです。




#include<stdio.h>
#include<vector>
#include<bitset>
double myMax=1000000000;//最大値
double memoMoveTime[31][31][9];//mMT[都市1][都市2][チケットi]で移動したときにかかる時間
double nowTime[31][257];//[都市i][チケットの状態s]で到達できた最短タイム
double tickets[9];//チケットデータ
int n,m,p,a,b;//チケット数、都市数、道路数、出発地、目的地
std::vector<int> permMemo[9];//[k枚]チケットを使った場合の組み合わせ
void calc(){
int permMax=1<<n;//チケットで作れる組み合わせの総数
int nextPerm,cHash;
double nextTime;
for(int k=0;k<n;k++){
	//今のところk枚チケットを使った
	for(int c1=0;c1<m;c1++){
		//都市c1~スタート
		for(int c2=0;c2<m;c2++){
			//都市c2への移動
			if(memoMoveTime[c1][c2][0]==myMax)continue;//道が通じてなかった
			for(int cNo=0;cNo<n;cNo++){
				//cNo番目のカードを使う
				cHash=1<<(cNo);//cNo番目のカードを使えるか
				for(int u=0;u<permMemo[k].size();u++){
					//チケットの組perm
					int perm=permMemo[k][u];
					if((perm&cHash)!=0)continue;//このカードは使用済みなので次へ
					if(nowTime[c1][perm]==myMax)continue;//この都市へ到達してないので次へ
					nextPerm=perm|cHash;
					nextTime=nowTime[c1][perm]+memoMoveTime[c1][c2][cNo];
					if(nowTime[c2][nextPerm]>nextTime){
						nowTime[c2][nextPerm]=nextTime;
					}
				}
			}
		}
	}
}
double ans=myMax;
for(int p=0;p<permMax;p++){
	ans=ans>nowTime[b][p]?nowTime[b][p]:ans;
}
if(ans>=myMax){
	printf("Impossible\n");
}else{
	printf("%lf\n",ans);
}
}
void setData(){
//データの初期化を行う
//チケットデータの読み込み
for(int i=0;i<n;i++){
	scanf("%lf",&tickets[i]);
}
//移動にかかる時間の初期化
int c1,c2,cNo;
double time;
for(c1=0;c1<m;c1++){
	for(c2=0;c2<m;c2++){
		for(cNo=0;cNo<n;cNo++){
			memoMoveTime[c1][c2][cNo]=myMax;
		}
	}
}
//移動にかかる時間の設定
for(int i=0;i<p;i++){
	scanf("%d %d %lf",&c1,&c2,&time);
	c1--;
	c2--;
	for(cNo=0;cNo<n;cNo++){
		memoMoveTime[c1][c2][cNo]=memoMoveTime[c2][c1][cNo]=time/tickets[cNo];
	}
}
for(c1=0;c1<m;c1++){
	for(cNo=0;cNo<256;cNo++){
		nowTime[c1][cNo]=myMax;
	}
}
nowTime[a][0]=0;
for(int i=0;i<=n;i++)permMemo[i].clear();
std::bitset<9> b;
for(int p=0;p<(1<<n);p++){
	b=p;
	permMemo[b.count()].push_back(p);
}
}
int main(){
while(1){
	scanf("%d %d %d %d %d",&n,&m,&p,&a,&b);//基礎データ読み込み
	if(n+m+p+a+b==0)break;
	a--;//扱いやすいよう0ベースにする
	b--;
	
	setData();
	calc();
}
}