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

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

AOJ再挑戦31~35 - (2014/01/28 (火) 09:22:03) の最新版との変更点

追加された行は青色になります。

削除された行は赤色になります。

 *問31 Weight
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0031&lang=jp
 天秤で重さを図るときの問題
 
 解法
 2^nで考えたらnのビットがたってるものだけ出力。
 あとはn/2で割ったあとnが0でないならまだのせるものがあるのでスペースを出力。
 
  
  #include<stdio.h>
  
  int main(){
  	int n;
  	while(scanf("%d",&n)!=EOF){
  		int a=1;
   		while(n!=0){
  			if(n%2==1){
  				printf("%d",a);
  				n/=2;
  				if(n>0)printf(" ");
   			}else{
  				n/=2;
  			}
  			a*=2;
   		}
  		printf("\n");
  	}
  }
 
 
 
 *問32 Plastic Board
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0032
 長方形とひし形とそれ以外を判別して数える問題
 
 **解法
 長方形なら3平方が成り立ち成り立たないなら、ひし形の可能性しかない。
 ひし形なら隣り合う2辺は同じ長さ。
 そうでないならひし形でもない。
 
  #include<stdio.h>  
  int main(){
   	int a,b,c,ans1=0,ans2=0;
  	while(scanf("%d,%d,%d",&a,&b,&c)!=EOF){
  		if(a*a+b*b==c*c){
  			ans1++;
  		}else if(a==b){
   			ans2++;
  		}
  	}	
  	printf("%d\n%d\n",ans1,ans2);
  }
 
 
 *問33 Ball
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0033
 ボールを左右に分けていく問題。
 
 解法
 優先して左に入れる、入らなければ右に入らないか試す。
 両方駄目ならどうやっても入らない。
 それだけ、計算量は一回のボールセットで10。
 
  #include<stdio.h> 
  int main(){
  	int n,l,r,b;
  	scanf("%d",&n);
  	while(n--){
   		l=r=0;//左のほうが常に大きくなるようにする入らなければ右
 		bool ok=true;
   		for(int i=0;i<10;i++){
  			scanf("%d",&b);
  			if(l<b){
  				l=b;
   			}else if(r<b){
  				r=b;
  			}else{
  				ok=false;
   			}
  		}
  		printf("%s\n",ok?"YES":"NO");
  	}
  }
 
 
 
-*Railway Lines
+*問34 Railway Lines
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0034
 電車がすれ違う区間をこたえる問題。
 解法
 両方の電車の相対速度で両電車は違づくのでそれからすれ違うタイムが出てあとはすれ違うポイントを探すだけです。
 
  #include<stdio.h>
  
  int main(){
  	double Ls[11],L,v1,v2;
   	while(1){
  		Ls[0]=0;
  		if(scanf("%lf,",&Ls[1])==EOF)break;
  		for(int i=2;i<11;i++){
  			scanf("%lf,",&L);
  			Ls[i]=Ls[i-1]+L;
   		}
  		scanf("%lf,%lf",&v1,&v2);
  		double p=v1*Ls[10]/(v1+v2);
  		int ans=0;
  		for(int i=0;i<11;i++){
   			if(p<=Ls[i]){
  				ans=i;
  				break;
  			}
  		}
   		printf("%d\n",ans);
  	}
+ }
+
+
+
+*問35  Is it Convex?
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0035
+凸多角形の判定問題
+凸多角形をいいなおせば、頂点で曲がるときかならず右曲りか左曲りに曲がりどちらかが4つ連続すればそれは凸です。
+外積で判定するだけです。
+
+
+ #include<stdio.h>
+ 
+ int main(){
+ 	double xs[4],ys[4];
+ 	while(1){
+ 		if(scanf("%lf,%lf",&xs[0],&ys[0])==EOF)break;
+ 		for(int i=1;i<4;i++){
+  			scanf(",%lf,%lf",&xs[i],&ys[i]);
+ 		}
+ 		int count=0;
+ 		for(int i=0;i<4;i++){
+ 			int p1=i;
+ 			int p2=(i+1)%4;
+  			int p3=(i+2)%4;
+ 			double dx2,dy2,dx3,dy3;
+ 			dx2=xs[p2]-xs[p1];
+ 			dy2=ys[p2]-ys[p1];
+ 			dx3=xs[p3]-xs[p1];
+  			dy3=ys[p3]-ys[p1];
+ 			count+=(dx2*dy3-dx3*dy2>0?1:-1);
+ 		}
+  		printf("%s\n",count==4||count==-4?"YES":"NO");
+  	}
  }