Topcoder SRM 492 550 "TimeTravellingGardener"

問題：http://www.topcoder.com/stat?c=problem_statement&pm=11060

プラクティス．

一直線上に生えている木の高さとそれぞれの木の間の距離が与えられる．任意の木の高さを下げることができるとき，それぞれの木の高さが同じ割合で増減した状態にするために木の高さを下げる数の最小値を求める．

まず，最悪の場合の答えとして最小の高さの一つ以外のすべての高さを下げることがあげられる．その他の場合，ある二つの木の高さについてその直線の式を求め，各木の位置における望まれる木の高さを直線の式から求める．木の高さは下げることしかできず，最低でも地面までのため，望まれる木の高さがすでにもとの木の高さよりも小さい場合や，望まれる木の高さが地面よりも小さい（0よりも小さい）場合は答えとして適切でない．ある直線の式においてすべての木の高さが望まれる木の高さ以上の場合，高さが等しくない木の数を数え上げて答えとする．

public class TimeTravellingGardener {

	public int determineUsage(int[] distance, int[] height) {
		int n = height.length;
		int[] d = new int[n];
		for (int i = 1; i < n; ++i) {
			d[i] += d[i - 1] + distance[i - 1];
		}
		int result = Integer.MAX_VALUE;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				int r = 0;
				Line line = new Line(new Point(d[i], height[i]), new Point(
						d[j], height[j]));
				for (int k = 0; k < n; ++k) {
					if (i != k && j != k) {
						double exph = line.y(d[k]);
						if (exph < -1e-5 || (double)height[k] < exph - 1e-5) {
							r = Integer.MAX_VALUE;
							break;
						}
						if ((double)height[k]- exph > 1e-5) {
							++r;
						}
					}
				}
				result = Math.min(result, r);
			}
		}
		return result==Integer.MAX_VALUE?n-1:result;
	}

	class Line {
		double a, b;

		Line(Point p1, Point p2) {
			if (p1.y == p2.y) {
				a = 0;
				b = p1.y;
			} else {
				a = ((double) p2.y - p1.y) / (p2.x - p1.x);
				b = (double)p1.y - a * p1.x;
			}
		}

		double y(int x) {
			return a * x + b;
		}
	}

	class Point {
		int x, y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}