Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

AOJ 0273 - Cats Going Straight II


解法 :

双対グラフを作ってbfs すれば良い... が, グラフ構築バグりまくってます. 悲しい.
(まだWA...)
朝にバグ取ります...

コード :

int main()
{
	int N, M;
	
	while (scanf("%d %d", &N, &M) && N){
		vector<Point> P(N);
		vector<int> to[128];
		bool exist[128][128] = {0};
		
		for (int i = 0; i < N; i++){
			scanf("%lf %lf", &P[i].x, &P[i].y);
			P[i].id = i;
		}
		
		for (int i = 0; i < M; i++){
			int x, y;
			scanf("%d %d", &x, &y);
			to[--x].push_back(--y);
			to[y].push_back(x);
			exist[x][y] = exist[y][x] = 1;
		}
		
		Polygon Q = P;
		Q = conhel(Q);
		
		vector<int> belong[128][128];
		for (int i = 0; i < Q.size(); i++){
			int u = Q[i].id, v = Q[(i + 1) % Q.size()].id;
			belong[u][v].push_back(0);
			belong[v][u].push_back(0);
		}
		int k = 1;
		set<vector<int> > s;
		
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				if (P[j] < P[i] && exist[i][j] && belong[i][j].size() < 2){
					vector<int> v;
					v.push_back(i);
					v.push_back(j);
					while (1){
						int nextP = -1;
						int vv = v[v.size() - 1], uu = v[v.size() - 2];
						for (int l = 0; l < to[vv].size(); l++){
							if (to[vv][l] == vv || to[vv][l] == uu) continue;
							if (ccw(P[uu], P[vv], P[to[vv][l]]) < 0){
								if (nextP == -1 || getCos(P[uu] - P[vv], P[to[vv][l]] - P[vv]) > getCos(P[uu] - P[vv], P[nextP] - P[vv])) nextP = to[vv][l];
							}
						}
						assert(nextP != -1);
						if (nextP == i) break;
						v.push_back(nextP);
					}
					vector<int> ss = v;
					sort(ss.begin(), ss.end());
					if (s.find(ss) != s.end()) continue;
					else s.insert(ss);
					for (int it = 0; it < v.size(); it++){
						int uu = v[it], vv = v[(it + 1) % v.size()];
						belong[uu][vv].push_back(k);
						belong[vv][uu].push_back(k);
					}
					k++;
				}
			}
		}
		vector<int> G[1024];
		
		for (int i = 0; i < N; i++){
			for (int j = i + 1; j < N; j++){
				if (belong[i][j].size()){
					int u = belong[i][j][0], v = belong[i][j][1];
					G[u].push_back(v);
					G[v].push_back(u);
				}
			}
		}
		
		int ans = 0;
		int done[1024];
		fill(done, done + 1024, -1);
		queue<pair<int, int> > q;
		
		for(q.push(make_pair(0, 0)); q.size(); q.pop()){
			pair<int, int> x = q.front();
			if (~done[x.first]) continue;
			done[x.first] = x.second;
			ans = max(ans, x.second);
			
			for (int i = 0; i < G[x.first].size(); i++){
				q.push(make_pair(G[x.first][i], x.second + 1));
			}
		}
		
		printf("%d\n", ans);
	}
	
	return (0);
}