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); }