Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-20SRM368, SRM369 (Practice)

SRM 368 PolylineUnion

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

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

  • 幾何ゲーから逃げない。
    • 点と点が一致するか
      • 単純に全部調べる
    • 点が線分のどこかと一致するか
      • 内積が0以上かつ外積が0かどうか調べる
    • 線分と線分が交差するか
      • 線分交差判定を書く。
      • 2点がもう一方の線分それぞれのどちら側かを外積を使って判定x2 両方共逆側になってたら交差してる
  • サンプル通った。
    • 交差判定とかintで書いちゃったけど大丈夫かな・・・
    • 条件を見ると (座標) <= 10000 みたいなこと書いてある。
      • 最大で(座標^2) <= 100,000,000 だからintでも大丈夫だろう
    • ある折れ線とある折れ線が交差したかどうかはUnionFindで管理
  • 出した。
    • WA食らう
    • よく見ると、線分の交差判定で (外積) * (外積) < 0 という計算をしてる。
      • それじゃintだとダメだよ・・・
        • (座標) ^ 4 になるので
      • longに直したら通った
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class PolylineUnion {

	class UnionFind {
		int[] parent, rank;
		UnionFind(int n) {
			parent = new int[n];
			rank = new int[n];
			for (int i = 0 ; i < n ; i++) {
				parent[i] = i;
				rank[i] = 0;
			}
		}
		
		int find(int x) {
			if (parent[x] == x) {
				return x;
			}
			parent[x] = find(parent[x]);
			return parent[x];
		}
		
		void unite(int x, int y) {
			x = find(x);
			y = find(y);
			if (x == y) {
				return;
			}
			if (rank[x] < rank[y]) {
				parent[x] = y;
			} else {
				parent[y] = x;
				if (rank[x] == rank[y]) {
					rank[x]++;
				}
			}
		}
		boolean issame(int x, int y) {
			return (find(x) == find(y));
		}
	}
	
	public boolean intersects(long qx, long qy, long ax, long ay, long bx, long by) {
		long dx1 = (qx - ax);
		long dy1 = (qy - ay);
		long dx2 = (bx - qx);
		long dy2 = (by - qy);
		long dot = dx1 * dx2 + dy1 * dy2;
		if (dot >= 0) {
			if (dx1 * dy2 - dx2 * dy1 == 0) {
				return true;
			}
		}
		return false;
	}

	
	public boolean intersectsD(long ax, long ay, long bx, long by, long cx, long cy, long dx, long dy) {
		long lx = bx - ax;
		long ly = by - ay;
		long px = cx - ax;
		long py = cy - ay;
		long qx = dx - ax;
		long qy = dy - ay;
		long crossA = lx * py - ly * px;
		long crossB = lx * qy - ly * qx;
		if (crossA * crossB < 0) {
			return true;
		}
		return false;
	}
	
	public boolean intersects(long ax, long ay, long bx, long by, long cx, long cy, long dx, long dy) {
		return (intersectsD(ax, ay, bx, by, cx, cy, dx, dy) && intersectsD(cx, cy, dx, dy, ax, ay, bx, by));
	}
	public int countComponents(String[] polylines) {
		String line = "";
		for (String p : polylines) {
			line += p;
		}
		String[] lines = line.split(" ");
		int len = lines.length;
		UnionFind uf = new UnionFind(len);
		int[][] px = new int[len][];
		int[][] py = new int[len][];
		for (int i = 0 ; i < len ; i++) {
			String[] polys = lines[i].split("-");
			int pl = polys.length;
			px[i] = new int[pl];
			py[i] = new int[pl];
			for (int p = 0 ; p < pl ; p++) {
				String[] pt = polys[p].split(",");
				px[i][p] = Integer.valueOf(pt[0]);
				py[i][p] = Integer.valueOf(pt[1]);
			}
		}
		
		for (int i = 0 ; i < len ; i++) {
			for (int j = i + 1 ; j < len ; j++) {
				int al = px[i].length;
				int bl = px[j].length;
				boolean intersects = false;
				points: for (int a = 0 ; a < al ; a++) {
					for (int b = 0 ; b < bl ; b++) {
						if (px[i][a] == px[j][b] && py[i][a] == py[j][b]) {
							intersects = true;
							break points;
						}
					}
				}
				if (!intersects) {
					pointline:
					{
						for (int a = 0 ; a < al ; a++) {
							for (int b = 0 ; b < bl - 1 ; b++) {
								if (intersects(px[i][a], py[i][a], px[j][b], py[j][b], px[j][b+1], py[j][b+1])) {
									intersects = true;
									break pointline;
								}
							}
						}
						for (int b = 0 ; b < bl ; b++) {
							for (int a = 0 ; a < al - 1 ; a++) {
								if (intersects(px[j][b], py[j][b], px[i][a], py[i][a], px[i][a+1], py[i][a+1])) {
									intersects = true;
									break pointline;
								}
							}
						}
					}
				}
				if (!intersects) {
					lineline: for (int a = 0 ; a < al - 1 ; a++) {
						for (int b = 0 ; b < bl - 1 ; b++) {
							if (intersects(px[i][a], py[i][a], px[i][a+1], py[i][a+1], px[j][b], py[j][b], px[j][b+1], py[j][b+1])) {
								intersects = true;
								break lineline;
							}
						}
					}
				}
				if (intersects) {
					uf.unite(i, j);
				}
 			}
		}
		
		int cnt = 0;
		boolean[] done = new boolean[len];
		for (int i = 0 ; i < len ; i++) {
			if (done[i]) {
				continue;
			}
			done[i] = true;
			for (int j = 0 ; i < len ; i++) {
				if (uf.issame(i, j)) {
					done[j] = true;
				}
			}
			cnt++;
		}
		Set<Integer> gset = new HashSet<Integer>();
		for (int i = 0 ; i < len ; i++) {
			gset.add(uf.parent[i]);
		}	
		return gset.size();
	}
}