Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-06SRM300台を練習していく part8

SRM 319 BusSeating

|  SRM 319 BusSeating - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 319 BusSeating - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6715

各空席の位置を座標に変換して、組み合わせを全探索。


public class BusSeating {

	public double getArrangement(String leftRow, String rightRow) {
		int ptnum = 0;
		int[] px = new int[20];
		int[] py = new int[20];
		
		for (int i = 0 ; i < 10 ; i++) {
			if (leftRow.charAt(i) == '-') {
				px[ptnum] = i;
				py[ptnum] = 0;
				ptnum++;
			}
			if (rightRow.charAt(i) == '-') {
				px[ptnum] = i;
				py[ptnum] = 2;
				ptnum++;
			}
		}
		
		double min = 999999999.9d;
		for (int a = 0 ; a < ptnum ; a++) {
			for (int b = a+1 ; b < ptnum ; b++) {
				for (int c = b+1 ; c < ptnum ; c++) {
					double ab = Math.hypot(px[a] - px[b], py[a] - py[b]);
					double bc = Math.hypot(px[b] - px[c], py[b] - py[c]);
					double ca = Math.hypot(px[c] - px[a], py[c] - py[a]);
					if (ab + bc + ca < min) {
						min = ab + bc + ca;
					}
				}
			}
		}
		if (min >= 999999999) {
			return 0;
		}
		return min;
	}
}