kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Circles Intersection(AOJ No.0023), Physical Experiments(AOJ No.0024), Hit and Blow(AOJ No.0025), Dropping Ink(AOJ No.0026)

Online Judge

リポジトリ

Circles Intersection(AOJ No.0023)

中心(xa,ya)、半径raの円Aと、中心(xb,yb)、半径rbの円Bが与えられたとき、
B が A の中にあるとき 2、
A が B の中にあるとき -2、
A の円周と B の円周が交わっている場合 1、
A と B が重なっていないとき 0
を出力する。

アルゴリズム

2つの円の半径がそれぞれr,r'とし，2つの円の中心間の距離をdとすると，
１．離れている ⇔ r+r'r' ? 2 : -2; //r=r'にはならない(r=r'なら前提５．が成立しないので)
otherwise ⇒ return 1;
※題意は、AがBを包含していても、BがAを包含していても、内接の場合もreturn 1。ちょい分かりにくかった。

コード

d, r+r' r-r'の2乗を使って判定した。
2013/04/14 修正したライブラリで確認した。

import java.util.*;
import java.awt.geom.Point2D;
public class aoj0023 {
	static Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int n = stdin.nextInt();
		while( n-- > 0 ){
			Circle a = new Circle(stdin.nextDouble(), stdin.nextDouble(), stdin.nextDouble());
			Circle b = new Circle(stdin.nextDouble(), stdin.nextDouble(), stdin.nextDouble());
			int ans;
			switch(a.positionalRelation(b)){
			case Separated:		ans = 0; break;
			case FullIncluded:	ans = (a.r > b.r ? 2 : -2); break;
			default:	                ans = 1;
			}
			System.out.println( ans );
		}
	}
	enum PosRelation { Separated, Circumscribed, CrossAt2Point, Inscribed, FullIncluded; }
	@SuppressWarnings("serial") public static class Point extends Point2D.Double {
		public Point(double x, double y){ super(x,y); }
	} //class Point

	public static class Circle{
		public final Point o;
		public double r;
		public Circle(double x, double y, double r){ this.o = new Point(x,y); this.r = r; }
		public final PosRelation positionalRelation(Circle c){
			double d2 = o.distanceSq(c.o);
			double dp2 = (r + c.r)*(r + c.r);
			if(d2 > dp2) return PosRelation.Separated;
			if(d2 == dp2) return PosRelation.Circumscribed;
			double dn2 = (r - c.r)*(r - c.r);
			if(dn2 < d2) return PosRelation.CrossAt2Point; //d < dp
			if(d2 == dn2) return PosRelation.Inscribed;
			return PosRelation.FullIncluded; //d < dn
		}
	}
}

Physical Experiments(AOJ No.0024)

速度vで地面にぶつけると壊れる球がある。球を壊すには最低何階の高さから落とせばよいか?
ただし、N階の高さは5N-5。

アルゴリズム

2a(x-x_0)=v^2 -v_0^2に当てはめると
\begin{array}{rl}-2\cdot 9.8(0-(5N-5))&&=v^2 \\ N &&= (\frac{v^2}{2\cdot 9.8}+5)/5 \end{array}
従って、 N = \lceil v^2 /98 + 1 \rceil

コード

N = \lceil v^2 /98 + 1 \rceil だとwrong answerになってしまった。
計算誤差なのかなぁ...?

import java.util.*;
public class aoj0024 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(stdin.hasNext()){
			double v = stdin.nextDouble();
			System.out.println( (int) Math.ceil( (v*v/19.6 + 5)/5 ) );
			// ceil( v*v/98 + 1 )ではwrong answerだった
		}
	}
}

Hit and Blow(AOJ No.0025)

a_1 a_2 a_3 a_4, b_1 b_2 b_3 b_4が与えられたときのHit, Blowの数をこたえる。
a_i = b_i ならHit、 \begin{array}{lr}a_i = b_j &&(i\neq j) \end{array}ならBlow

アルゴリズム

bを読み込むときにHitを計算。
a, bをソートして、レンジ外になるまで次のループを回す。
a[ai]=b[bi]ならBlow++,ai++,bi++
a[ai]>b[bi]ならbi++
a[ai]

コード

import java.util.*;
import java.util.*;
public class aoj0025 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		int[] a = new int[4], b = new int[4];
		while(stdin.hasNext()){
			int hit = 0, blow = 0;
			for(int i=0; i<4; ++i) a[i] = stdin.nextInt();
			for(int i=0; i<4; ++i){
				b[i] = stdin.nextInt();
				if(a[i] == b[i]) ++hit;
			}
			Arrays.sort(a); Arrays.sort(b);
			int ai = 0, bi =0;
			while( ai < a.length && bi < b.length ){
				if(a[ai] == b[bi]){ ++blow; ++ai; ++bi; }
				else if(a[ai] > b[bi]) ++bi;
				else ++ai;
			}
			blow -= hit;
			System.out.println(hit + " " + blow);
		}
	}
}

Dropping Ink(AOJ No.0026)

10×10の白紙(濃度0)が与えられ、インクを落とす座標(x,y)とインクのサイズ(small, medium large)が与えられる。
インクを落とすと次のように濃度が増える。
small \begin{array}{|c|c|c|} \hline 0 & +1 & 0 \\\hline +1 & +1 & +1 \\\hline 0 & +1 & 0 \\\hline \end{array}　　medium \begin{array}{|c|c|c|} \hline +1 & +1 & +1 \\\hline +1 & +1 & +1 \\\hline +1 & +1 & +1 \\\hline \end{array}　　large \begin{array}{|c|c|c|c|c|} \hline 0 & 0 & +1 & 0 & 0 \\\hline 0 & +1 & +1 & +1 & 0 \\\hline +1 & +1 & +1 & +1 & +1 \\\hline 0 & +1 & +1 & +1 & 0 \\\hline 0 & 0 & +1 & 0 & 0 \\\hline \end{array}
濃度0のマスの数と、最大濃度を求める。

コード

周り2マスを大目にとっておいて(14×14)レンジ外判定をしなくて済むようにした。

import java.util.*;
public class aoj0026 {
	static final Scanner stdin = new Scanner(System.in);
	static final int N = 12;
	static int[][] map = new int[N+2][N+2];
	public static void main(String[] args) {
		for(int i=2; i < N; ++i) Arrays.fill(map[i], 2, N, 0);
		while(stdin.hasNext()){
			String[] a = stdin.nextLine().split(",");
			int x = Integer.parseInt(a[0]) + 2, y = Integer.parseInt(a[1]) + 2;
			switch( Integer.parseInt(a[2]) ){
			case 1: small(x,y); break;
			case 2: medium(x,y); break;
			case 3: large(x,y); 
			}
		}
		int zero = 0, max = 0;
		for(int i=2; i<N; ++i){
			for(int j=2; j<N; ++j){
				if(map[i][j] == 0) ++zero;
				max = Math.max(max, map[i][j]);
			}
		}
		System.out.println(zero + "\n" + max);
	}
	static void small(int x, int y){
		for(int i=-1; i<=1; ++i) ++map[y][x+i];
		++map[y+1][x]; ++map[y-1][x];
	}
	static void medium(int x, int y){
		small(x,y);
		++map[y+1][x+1]; ++map[y+1][x-1]; ++map[y-1][x+1]; ++map[y-1][x-1];
	}
	static void large(int x, int y){
		medium(x,y);
		++map[y+2][x]; ++map[y-2][x]; ++map[y][x+2]; ++map[y][x-2];
	}
}