AOJ 1359 Wall Clocks

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1359

解法

各点から半直線が2本出て，長方形の周上の2点で交わるが，それをそのまま処理すると面倒．
なので，(0, 0) -> (0, d) -> (w, d) -> (w, 0) -> (0, 0) という4辺を展開して，[0, 2(w+d)] という数直線上の区間にしてしまうと楽になる．
半直線は 45度 なので，展開後の座標は簡単な計算により求まる．
各点 i から見える範囲が [li, ri] とすると，ri の 昇順にソートしてやるとよい．最初にどこに時計を置くかを決めれば，あとは時計回り（つまり数直線の右方向）に，置いた時計が見えなくなるまで飛ばして，見えなくなったら追加することで解が得られる．
あとは，最初に時計を置く位置を全探索すれば最適解が求まる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int main() {
    int n, w, d;
    cin >> n >> w >> d;
    vector<pii> v;
    for(int i=0; i<n; ++i) {
        int x, y;
        char f;
        cin >> x >> y >> f;
        if(f == 'W') {
            v.emplace_back(x + y, -x + y);
        } else if(f == 'N') {
            v.emplace_back(2*d + x - y, x + y);
        } else if(f == 'E') {
            v.emplace_back(2*(d+w) - x - y, 2*d + x - y);
        } else {
            v.emplace_back(2*(d+w) - x + y ,2*(d+w) - x - y);
        }
    }
    sort(v.begin(), v.end());
    int L = 2*(w + d);
    int res = 1e9;
    for(int i=0; i<n; ++i) {
        auto tmp = v;
        for(int j=i-1; j>=0; --j) {
            if(tmp[j].first < tmp[i].first) {
                tmp[j].first += L;
                tmp[j].second += L;
            }
        }
        sort(tmp.begin(), tmp.end());
        int cnt = 1;
        int now = tmp[0].first;
        for(int j=0; j<n; ++j) {
            if(tmp[j].second > now) {
                now = tmp[j].first;
                cnt++;
            }
        }
        res = min(res, cnt);
    }
    cout << res << endl;
}