AOJ再挑戦76～80 - c21coterie @ ウィキ

問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

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

#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

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