Triangle and Circle(AOJ No.0153), Sum of Cards(AOJ No.0154), Spider Jin(AOJ No.0155), Moats around the Castle(AOJ No.0156)

リポジトリ

Triangle and Circle(AOJ No.0153)

１つの三角形(頂点座標×3)と１つの円(中心座標＋半径)が与えられたときの位置関係を↓で求める。

• 円が三角形に含まれる場合 a
• 三角形が円に含まれる場合 b
• それ以外の場合で、共通部分がある場合には c
• 共通部分がない場合には d

半径、座標はすべて10,000以下の整数で与えられる。

コード

ライブラリ流用。WAを数十回出した。
誤差のせいだと思っていたけど、線分と点の距離を求める際に使用した正射影を求める関数がバグってただけだった。(´・ω・`)

import java.awt.geom.Point2D;
import java.util.*;
public class aoj0153 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) { 
		Point[] tri = {new Point(0,0), new Point(0,0), new Point(0,0)};
		Circle c = new Circle(0,0,0);
		char ans = 0;
		while(true){
			tri[0].set(stdin.nextDouble(), stdin.nextDouble());
			if(tri[0].x == 0 && tri[0].y == 0) break;
			tri[1].set(stdin.nextDouble(), stdin.nextDouble());
			tri[2].set(stdin.nextDouble(), stdin.nextDouble());
			c.set(stdin.nextDouble(), stdin.nextDouble(), stdin.nextDouble());
			switch(c.positionalRelation(tri)){
			case Separated: ans = 'd'; break;
			case PolygonInCircle: ans = 'b'; break;
			case Circumcircle: ans = 'b'; break;
			case PartialCross: ans = 'c'; break;
			case Incircle: ans = 'a'; break;
			case CircleInPolygon: ans = 'a'; break;
			//default: break;
			}
			System.out.println(ans);
		}
	}
	public static final double EPS = 1e-10;
	public static boolean equal(double a, double b){ return Math.abs(a-b) < EPS; }	// a == b
	public static boolean less(double a, double b){ return a - b < -EPS; }			// a < b
	public static boolean leq(double a, double b){ return a - b < EPS; }			// a <= b
	public static boolean greater(double a, double b){ return less(b,a); }			// a > b
	public static enum PosRelation {
		Separated, PolygonInCircle, Circumcircle, PartialCross, Incircle, CircleInPolygon;
	}
	@SuppressWarnings("serial") public static class Point extends Point2D.Double {
		public Point(double x, double y){ super(x,y); }
		public Point(Point p){ super(p.x, p.y); }
		public final void set(double x, double y){ this.x = x; this.y = y; }
		public final double normsq(){ return x*x + y*y; }
		public final Point add(Point p){ return new Point( x + p.x, y + p.y ); }
		public final Point sub(Point p){ return new Point( x - p.x, y - p.y ); }
		public final Point mul(double k){ return new Point( k*x, k*y ); }
		public final double cross(Point p){ return x * p.y - y * p.x; }
		public final double dot(Point p){ return x * p.x + y * p.y; }
		public final Point projection(Line l){
			Point a = l.dirV();
			Point b = this.sub(l.start);
			return l.start.add(a.mul(a.dot(b)/a.normsq()));
		}
		public final double distancePS(Line s){
			Point proj = projection(s);
			return proj.intersectsPS(s) ? distance(proj) : Math.min(distance(s.start), distance(s.end));
		}
		public final boolean intersectsPS(Line s) {
			return equal(s.start.distance(this) + this.distance(s.end), s.end.distance(s.start)); //三角不等式で等号が成り立つとき
		}
	} //class Point
	public static class Line{
		private final Point start;
		private final Point end;
		public Line(Point start, Point end){ this.start = new Point(start); this.end = new Point(end); }
		public Point dirV() { return end.sub(start); } //directional vector
	} //class Line
	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 void set(double x, double y, double r){ o.x = x; o.y = y; this.r = r; }
		public PosRelation positionalRelation(final Point[] polygon){
			final int n = polygon.length;
			double[] dists = new double[n];
			boolean flag = true, eq = true;
			for(int i = 0; i < n; ++i){
				dists[i] = o.distance(polygon[i]);
				if(!equal(dists[i], r)) eq = false;
				if(greater(dists[i], r)) flag = false;
			}
			if(eq) return PosRelation.Circumcircle; //外接円
			if(flag) return PosRelation.PolygonInCircle; //円が多角形を内包する

			for(int i = 0; i < n; ++i) dists[i] = o.distancePS(new Line(polygon[i], polygon[(i+1)%n]));

			eq = flag = true;
			if(contains(polygon, o)){
				for(double d: dists){
					if(!equal(d, r)) eq = false;
					if(less(d, r)) flag = false;
				}
				if(eq) return PosRelation.Incircle; //内接円
				if(flag) return PosRelation.CircleInPolygon; //多角形が円を内包する
			}else{
				for(double d: dists) if(leq(d, r)) flag = false;
				if(flag) return PosRelation.Separated; //分離
			}
			return PosRelation.PartialCross; //一部交差
		}
	}
	public static boolean contains(Point[] polygon, Point p) {
		boolean in = false;
		for (int i = 0, n = polygon.length; i < n; ++i) {
			Point a = polygon[i].sub(p), b = polygon[(i+1)%n].sub(p);
			if (a.y > b.y){ Point temp = b; b = a; a = temp; }
			if (a.y <= 0 && 0 < b.y) 
				if (a.cross(b) < 0) in = !in; //=0 -> a//b -> on 
			if (equal(a.cross(b), 0) && leq(a.dot(b), 0)) return true; //on edge
		}
		return in; //in out
	}
}

Sum of Cards(AOJ No.0154)

整数が書かれたカードが入った袋がある。
整数が書かれたカードは枚である。
いくつかのカードを袋から取り出したとき、取り出したカードの総和がnとなる組み合わせを求める。
制約

アルゴリズム

を使って総和をにする組み合わせ

について

答えは

コード

import java.util.*;
public class aoj0154 {
	static final Scanner stdin = new Scanner(System.in);
	static final int J = 1000;
	public static void main(String[] args) {
		int m;
		while((m = stdin.nextInt()) != 0){
			int[] a = new int[m+1], b = new int[m+1];
			for(int i = 1; i <= m; ++i){
				a[i] = stdin.nextInt();
				b[i] = stdin.nextInt();
			}
			int[][] LUT = solve(m, a, b);
			int g = stdin.nextInt();
			while(g-- >0) System.out.println(LUT[m][stdin.nextInt()]);
		}
	}
	static int[][] solve(int m, int[] a, int[] b){
		int[][] DP = new int[m+1][J+1];
		for(int i = 0; i <= m; ++i) Arrays.fill(DP[i], 0);
		DP[0][0] = 1;
		for(int i = 1; i <= m; ++i)
			for(int j = 0; j <= J; ++j)
				for(int k = 0; k <= b[i]; ++k)
					if(j-k*a[i] >= 0) DP[i][j] += DP[i-1][j-k*a[i]];
		return DP;
	}
}

Spider Jin(AOJ No.0155)

複数ビルがあって、ビル番号と座標が与えられる。
スパイダーマッがビルを経由して、ビルsからビルtに移動する最短経路を求める。
ダーマはビル間の距離が50以下でないとそのビル間は直接移動できない。
制約
最短経路は一意に決まる。
（整数）

アルゴリズム

ダイクストラでもいいが、同じグラフに対して、複数のs,tが与えられる仕様なので、ワーシャルフロイドで解いた。
浮動小数点使いたくなかったので距離の２乗でやってみたけど、テストケースが通らない。
「ビル間の距離が50以下」と「ビル間の距離の2乗が2500以下」って同値じゃないのヽ(。_°)ノ？

コード

import java.util.*;
public class aoj0155 {
	static final Scanner stdin = new Scanner(System.in);
	static final double INF = 1e10;
	static final double EPS = 1e-10;
	static boolean leq(double a, double b){ return a - b < EPS; }	// a <= b
	public static void main(String[] args) {
		int n;
		while((n = stdin.nextInt()) != 0){
			int[] x = new int[n], y = new int[n], i2n = new int[n];
			Map<Integer, Integer> n2i = new HashMap<Integer, Integer>(n+n);
			for(int i = 0; i < n; ++i){
				i2n[i] = stdin.nextInt();
				n2i.put(i2n[i], i);
				x[i] = stdin.nextInt();
				y[i] = stdin.nextInt();
			}
			double[][] G = new double[n][n];
			for(int i = 0; i < n; ++i)
				for(int j = 0; j < n; ++j){
					double dist = Math.hypot(x[i]-x[j], y[i]-y[j]);
					G[i][j] = (i != j && leq(dist, 50) ? dist : INF);
				}
			int m = stdin.nextInt();
			APSPResult res = FloydWarshall(G);
			while(m-- > 0){
				int s = n2i.get(stdin.nextInt()), t = n2i.get(stdin.nextInt());
				List<Integer> path = res.buildPath(s, t);
				if(path.isEmpty()){
					System.out.println("NA");
				}else{
					for(int i = 0; i < path.size(); ++i)
						System.out.print(i2n[path.get(i)] + (i < path.size() - 1 ? " " : "\n"));
				}
			}
		}
	}
	public static class Edge {
		protected int s; //source node		
		protected int d; //destination node
		protected int w; //edge weight
		Edge(int s, int d, int w){ set(s, d, w); }
		public final void set(int s, int d, int w){ this.s = s; this.d = d; this.w = w; }
	}
	public static class APSPResult{
		private double[][] dist; // dist[d]:= shortest path to d
		private int[][] prev; // back pointers
		@SuppressWarnings("unused") private boolean hasNegativeCycle;
		public APSPResult(double[][] dist, int[][] prev, boolean hasNegativeCycle){ set(dist, prev, hasNegativeCycle); }
		final private void set(double[][] dist, int[][] prev, boolean hasNegativeCycle){ this.dist = dist; this.prev = prev; this.hasNegativeCycle = hasNegativeCycle; }
		public List<Integer> buildPath(int s, int d){
			LinkedList<Integer> path = new LinkedList<Integer>();
			if(dist[s][d] < INF) for(int u = d; u >= 0; u = prev[s][u]) path.addFirst(u);
			return path;
		}
	}
	public static APSPResult FloydWarshall(double[][] G){
		int n = G.length;
		int[][] prev = new int[n][n];
		double[][] dist = new double[n][n];
		for(int i = 0; i < n; ++i){
			System.arraycopy(G[i], 0, dist[i], 0, n);
			dist[i][i] = 0;
			for(int j = 0; j < n; ++j) prev[i][j] = (G[i][j] != INF ? i : -1);
		}
		for(int k = 0; k < n; ++k){
			for(int i = 0; i < n; ++i){
				if(dist[i][k] >= INF) continue;
				for(int j = 0; j < n; ++j){
					double newDist = dist[i][k] + dist[k][j];
					if(dist[i][j] > newDist){
						dist[i][j] = newDist;
						prev[i][j] = prev[k][j];
					}
				}
			}
		}
		boolean hasNegativeCycle = false;
		for(int i = 0; i < n; ++i) if(dist[i][i] < 0){ hasNegativeCycle = true; break; }
		return new APSPResult(dist, prev, hasNegativeCycle);
	}
}

Moats around the Castle(AOJ No.0156)

のマップが与えられる。

• 「&」天守閣
• 「#」堀
• 「.」何も無い

どこでも移動可能だが、堀を上るときにコスト+1。
マップ外からスタートして天守閣にたどり着くまでにかかるコストをコストにしたときの、コストを答える。
制約

アルゴリズム

スタート位置がたくさんあるので、逆にゴールからスタートへ向かうBFSで解いた。
周りを「.」で囲んでから、周りの任意の位置からスタートしてもいいはず。
BFSを行う際、キューに座標を入れるが、コスト優先にした方が良さそうなので、コストも一緒にしてぶち込んでいる。
(x,y)に到達するのにかかる最小のコストを覚えておくが、コストの更新は、ポップする際ではなく、ぶち込むときに更新する。そうでないと、枝刈りタイミングが遅くなる。

コード

import java.util.*;
public class aoj0156 {
	final static Scanner stdin = new Scanner(System.in);
	final static char GOAL = '?', START = '&', SPACE = '.', FOSSE = '#';
	final static int INF = Integer.MAX_VALUE/2;
	final static int dy[] = {0, -1, 0, 1};
	final static int dx[] = {-1, 0, 1, 0};
	static int cost[][];
	static char map[][];
	public static void main(String[] args) {	
		while(true){
			int w = stdin.nextInt(), h = stdin.nextInt();
			if((w|h) == 0) break;
			stdin.nextLine(); //改行
			map = new char[h+2][w+2];
			int sx = 0, sy = 0;
			Arrays.fill(map[0], GOAL);
			for(int i = 1; i <= h; ++i){
				String line = stdin.nextLine();
				int idx = line.indexOf(START);
				if(idx >= 0){ sx = idx + 1; sy = i; }
				System.arraycopy(line.toCharArray(), 0, map[i], 1, w);
				map[i][0] = map[i][w+1] = GOAL;
			}
			Arrays.fill(map[h+1], GOAL);
			System.out.println(BFS(sx, sy));
		}
	}
	static int BFS(int sx, int sy){
		int h = map.length, w = map[0].length;
		cost = new int[h][w];
		for(int i = 0; i < h; ++i) Arrays.fill(cost[i], INF);

		Queue<int[]> q = new PriorityQueue<int[]>(h*w, new Comparator<int[]>(){  //o[0]:=x, o[1]:=y, o[2]:=cost
			@Override public int compare(int[] o1, int[] o2){ return o1[2] - o2[2]; }
		}); //cost優先
		cost[sy][sx] = 0;
		q.add(new int[]{sx, sy, 0});
		while(!q.isEmpty()){
			int[] p = q.poll();
			int x = p[0], y = p[1];
			if(map[y][x] == GOAL) return cost[y][x];
			for(int d = 0; d < dx.length; ++d) add(q, p, d);
		}
		return -1;
	}
	static void add(Queue<int[]> q, int[] p, int d){
		int x = p[0], y = p[1], c = cost[y][x], nx = x + dx[d], ny = y + dy[d];
		if(map[ny][nx] == FOSSE){
			if(map[y][x] != FOSSE){
				if(c + 1 < cost[ny][nx]){
					q.add(new int[]{nx, ny, c+1});
					cost[ny][nx] = c+1;
				}
			}else{
				if(c < cost[ny][nx]){
					q.add(new int[]{nx, ny, c});
					cost[ny][nx] = c;
				}
			}
		}else{
			if(c < cost[ny][nx]){
				q.add(new int[]{nx, ny, c});
				cost[ny][nx] = c;
			}
		}
	}
}