http://arc076.contest.atcoder.jp/tasks/arc076_c
わかったと思ったけどWA。よく考えてると2つの曲線の点がすべて違う辺に乗っているケースを見逃していた。
どっちの端点も長方形の辺に乗っている曲線についてのみ考えればよい。
曲線を適当に0,1,2...と名前を付けて、
曲線の端点を時計回りにsortする。
そのとき点のsort列がi,j,i,jになってはいけない。
これはstackで判断できる。
int W, H, N, M; ppi P[MAX_N]; bool used[MAX_N]; bool is_edge(int x, int y) { if(x == 0 || y == 0 || x == W || y == H) return true; else return false; } pair<pi, int> convert(pi p, int i) { pi res; int x = p.fst, y = p.sec; if(x == 0) res = pi(0, y); else if(y == H) res = pi(1, x); else if(x == W) res = pi(2, H - y); else res = pi(3, W - x); return make_pair(res, i); } void solve() { cin >> W >> H >> M; rep(i, 0, M) { int a, b, c, d; cin >> a >> b >> c >> d; if(!is_edge(a, b) || !is_edge(c, d)) continue; P[N++] = make_pair(pi(a, b), pi(c, d)); } vector<pair<pi, int>> vec; rep(i, 0, N) { vec.push_back(convert(P[i].fst, i)); vec.push_back(convert(P[i].sec, i)); } sort(all(vec)); stack<int> s; rep(i, 0, (int)vec.size()) { int a = vec[i].sec; if(!used[a]) { s.push(a); used[a] = true; } else { if(s.top() != a) { cout << "NO\n"; return; } s.pop(); } } cout << "YES\n"; }
stackは区間が部分的に重なっていないとき([a b],[c d]がa < cかつb < dを満たすような区間じゃないとき)に使えるイメージ。