---
tags: IOI
---
# IOI2007 Day1-2 洪水 (Flood)

定数倍高速化が本質(？)

## 問題文

https://www.ioi-jp.org/ioi/2007/problem/day1/flood-prob-j.pdf
https://oj.uz/problem/view/IOI07_flood

$N$ 個の点と $W$ 個の壁がある。
壁は点と点をつなぎ、座標軸と並行で、他の点をまたがない。
また、壁は他の壁と端点以外で共有点を持たない。$\Leftrightarrow$ 壁と壁の共有点は全て点になっている。
壁に囲まれていない外側の部分は水に浸かっている。
全領域が水に浸かるまで、以下が繰り返される。
- 片側のみ水に浸かっている壁が破壊される

最終的に残る壁を全て報告せよ。

$N ≤ 100000$

## 考察

とりあえずシミュレーションを考える。
適当な連結成分(？)について、必ず外側に入る点を見つけて、そこから外側を1周走査する。
同じ辺が2回出てきたらそれが答えで、出てきた辺は破壊 OR 水没だから消去する を繰り返していけば良い。
必ず外側に入る点を見つけるのがネックで、$O(N\log N + M)$ になる。
必ず外側に入る点は set<pair<int, int>> に入れて一番小さいのを選べば良い。

TLE 81点

81点なので定数倍が遅いことがわかる。
ネックの set<pair<int, int>> をあらかじめソートに変えると、10倍以上速くなって通る(？？？)

## 実装

115ms / 2000ms

https://oj.uz/submission/211954

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tuplis = array<int, 3>;
#define rep(b) for(int i = 0; i < b; i++)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)
 
 
struct wall{
    int to = -1, index;
    wall(){}
    wall(int to, int index): to(to), index(index){}
    bool exist() const { return to + 1; }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<pii> p(n);
    each(i, p) cin >> i.first >> i.second;
    vector<array<wall, 4>> g(n);
    int w;
    cin >> w;
    rep(w){
        int a, b;
        cin >> a >> b;
        a--; b--;
        int d = 0;
        if(p[a].first < p[b].first) d = 0;
        else if(p[a].first > p[b].first) d = 2;
        else if(p[a].second < p[b].second) d = 1;
        else d = 3;
        g[a][d] = {b, i};
        g[b][d ^ 2] = {a, i};
    }
    vector<bool> ans(w, 1);
    vector<int> sorted(n);
    iota(all(sorted), 0);
    sort(all(sorted), [&](int a, int b){ return p[a] < p[b]; });
    int i = 0;
    while(true){
        while(i < n && all_of(all(g[sorted[i]]), [](const wall& w){ return !w.exist(); })) i++;
        if(i == n) break;
        int start = sorted[i], at = start, d = 0;
        vector<pii> visit;
        if(!g[at][d].exist()) d = 1;
        do{
            if(!g[at][d].exist()){
                d++;
                d &= 3;
                continue;
            }
            visit.emplace_back(at, d);
            ans[g[at][d].index] = !ans[g[at][d].index];
            at = g[at][d].to;
            d--;
            d &= 3;
        }while(at != start);
        each(i, visit){
            int at, d;
            tie(at, d) = i;
            if(!g[at][d].exist()) continue;
            int at2 = g[at][d].to, d2 = d ^ 2;
            g[at][d].to = -1;
            g[at2][d2].to = -1;
        }
    }
    cout << accumulate(ans.begin(), ans.end(), 0) << '\n';
    rep(w) if(ans[i]) cout << i + 1 << '\n';
}