「AOJ再挑戦76~80」の編集履歴(バックアップ)一覧に戻る

AOJ再挑戦76~80 - (2014/02/02 (日) 17:52:05) のソース

*問76 Treasure Hunt2
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0076
宝の埋まってる座標をこたえる問題。

回転行列と漸化式の考えで求まります。
一般項を求めるのもありかもしれません。


 #include<stdio.h>
 #include<math.h>
 
 int main(){
 	double xs[1002],ys[1002],dx,dy,len;
 	xs[1]=1,ys[1]=0;
 	for(int i=1;i<=1000;i++){
 		dx=-ys[i];
  		dy=xs[i];
 		len=hypot(dx,dy);
 		xs[i+1]=xs[i]+dx/len;
 		ys[i+1]=ys[i]+dy/len;
 	}
 	int n;
 	while(1){
 		scanf("%d",&n);
 		if(n==-1)break;
 		printf("%lf\n%lf\n",xs[n],ys[n]);
 	}
 }



*問77 Run Length
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0077
圧縮された文字列を簡単な操作で複合する問題。
解法
@に出会ったらその処理をして出会わなかったらそのまま出力。
それだけ。

 #include<stdio.h>
 
 int main(){
 	char text[101],c;
  	while(scanf("%[^\n]%*c",text)!=EOF){
 		for(int i=0;text[i]!='\0';){
 			if(text[i]=='@'){
 				c=text[i+1]-'0';
 				while(c--)printf("%c",text[i+2]);
 				i+=3;
 			}else{
  				printf("%c",text[i]);
 				i++;
 			}
 		}
  		printf("\n");
 	}
 }


*問78 Magic Square
n*nの奇数サイズ魔法陣の生成を指定通りに実装する問題。
解法
生成手順は不思議なので結構追求したら深い意味はありそうですが。
実装する以外に特にすることがない問題でした。

 #include<stdio.h>
 #include<string.h>
 
 int map[15][15];
 void calc(int n){
 	memset(map,0,sizeof(map));
 	int x=n/2,y=n/2+1,t;
 	for(int i=1;i<=n*n;i++){
 		map[y][x]=i;
 		if(i==n*n)break;
 		x=(x+1)%n;
  		y=(y+1)%n;
 		while(map[y][x]!=0){
 			x=(x-1+n)%n;
 			y=(y+1)%n;
  		}
 	}
 	for(int i=0;i<n;i++){
 		for(int j=0;j<n;j++){
 			printf("%4d",map[i][j]);
 		}
 		printf("\n");
 	}
 }
 
 int main(){
 	int n;
 	while(1){
 		scanf("%d",&n);
  		if(n==0)break;
 		calc(n);
 	}	
 }


*問79 Area of Polygon
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0079
凸多角形の面積を求める問題。

解法
ヘロンの公式なんて使ったらこの問題めんどくさいだけです外積でいきましょう。

 #include<stdio.h> 
 int main(){
 	double xs[21],ys[21],ans=0;
	int i=0;
 	while(scanf("%lf,%lf",&xs[i],&ys[i])!=EOF){
 		ans+=i>0?xs[i]*ys[i-1]-xs[i-1]*ys[i]:0;
  		i++;
 	}
 	i--;
 	ans=(ans+xs[0]*ys[i]-xs[i]*ys[0])/2;
 	printf("%lf\n",ans>=0?ans:-ans);
 }




*問80 Third Root
qの3乗根を求める処理を指定通りに実装する問題。

解法
指定されたとおりに実装します。
こういう問題は再帰が一番楽です、C++で末尾最適化が実行されてるかはよくわかりませんが。

 #include<stdio.h>
 #include<math.h>
 const double EPS=0.00001;
 double calc(double x,double q){
 	return fabs(q-x*x*x)<(EPS*q)?x:calc(x-((x*x*x)-q)/(3*x*x),q);
 }
 
 int main(){
 	double q;
  	while(1){
 		scanf("%lf",&q);
 		if(q==-1)break;
 		printf("%.6lf\n",calc(q/2,q));
 	}
 }