AOJ 2310 - Rose Garden Witch

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

解法

直線を原点を中心に徐々に回転させていったとき， 分割数が増えるのは

..
.#

と

##
#.

の2パターン．

また，分割数が減るのは

#.
..

と

.#
##

の2パターン．

ただし，増えるパターンの点と減るパターンの点が同一直線上にあるときは，その点の前後で分割数は変わらないことに注意． これは減るパターンを先に処理することで対処することができる．

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct point
 7 {
 8   int n, d;
 9   bool inc;
10   point(int x, int y, bool z) : n(x), d(y), inc(z) {}
11   bool operator<(const point& that) const
12   {
13     const int x = n*that.d;
14     const int y = that.n*d;
15     if (x == y) {
16       return !inc && that.inc;
17     } else {
18       return x < y;
19     }
20   }
21 };
22 
23 int main()
24 {
25   int H, W;
26   cin >> H >> W;
27   vector<string> grid(H);
28   for (int i = 0; i < H; i++) {
29     cin >> grid[i];
30   }
31 
32   vector<point> ps;
33   for (int i = 0; i < H; i++) {
34     for (int j = 0; j < W; j++) {
35       if (grid[i][j] == '#'
36           && (i == 0 || grid[i-1][j] == '.')
37           && (j == 0 || grid[i][j-1] == '.')) {
38         ps.push_back(point(j, H-i, true));
39       } else if (grid[i][j] == '#'
40           && (i == H-1 || grid[i+1][j] == '.')
41           && (j == W-1 || grid[i][j+1] == '.')) {
42         ps.push_back(point(j+1, H-i-1, false));
43       } else if (grid[i][j] == '.'
44           && (i != 0 && grid[i-1][j] == '#')
45           && (j != 0 && grid[i][j-1] == '#')) {
46         ps.push_back(point(j, H-i, true));
47       } else if (grid[i][j] == '.'
48           && (i != H-1 && grid[i+1][j] == '#')
49           && (j != W-1 && grid[i][j+1] == '#')) {
50         ps.push_back(point(j+1, H-i-1, false));
51       }
52     }
53   }
54   sort(ps.begin(), ps.end());
55   int ans = 0;
56   int acc = 1;
57   for (vector<point>::const_iterator it = ps.begin(); it != ps.end(); ++it) {
58     if (it->inc) {
59       ++acc;
60       ans = max(ans, acc);
61     } else {
62       --acc;
63     }
64   }
65   cout << ans << endl;
66   return 0;
67 }