AOJ 1242 Area of Polygons
問題
方眼紙の格子点を結んだm角形が与えられる。
このm角形の内部を、0より大きな面積含む格子の個数を求めよ。
制約条件
座標の絶対値≦100
m≦100
方針
本当は平面走査でやるらしい。
自分は、線分をぐるりと引いて、境界線の格子を確定させて、
境界線以外の格子は塗りつぶした。
格子を塗り潰すのはBFSをすればよくて、
最初の1個目のマスは、点多角形包含判定をすればよい。
ソースコード
const int GETA = 2048; int n, mxx, mnx, mxy, mny; char flag[4096][4096]; inline void rec(int y, int x, int p){ queue<pi> q; q.push(mp(y, x)); flag[y][x] = p; while(!q.empty()){ y = q.front().first; x = q.front().second; q.pop(); rep(d, 4){ const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1}; int ny = y + dy[d], nx = x + dx[d]; if(ny < mnx || ny >= mxx || nx < mny || nx >= mxy || flag[ny][nx]) continue; flag[ny][nx] = p; q.push(mp(ny, nx)); } } } inline void draw(const P &a, const P &b, int rot){ int x = a.real(), y = a.imag(), X = b.real(), Y = b.imag(); int dx = X - x, dy = Y - y, mod = 0; vector<pi> v; for(; x < X; x++){ v.pb(mp(x, y)); mod += dy; while(mod > dx){ mod -= dx; v.pb(mp(x, ++y)); } if(mod == dx) mod -= dx, y++; } rep(i, v.size()){ int x = v[i].first, y = v[i].second; rep(it, rot){ swap(x, y); x *= -1; } const int dx[] = {0, -1, -1, 0}, dy[] = {0, 0, -1, -1}; flag[x + dx[rot] + GETA][y + dy[rot] + GETA] = 1; } } inline void draw(P a, P b){ rep(i, 4){ if(a.real() < b.real() && a.imag() <= b.imag()){ draw(a, b, i); return; } a *= P(0, -1); b *= P(0, -1); } } double area2(const G& g) { double A = 0; for (int i = 0; i < g.size(); ++i) A += cross(curr(g, i), next(g, i)); return A; } int main(){ while(cin >> n, n){ G g(n); int ans = 0; mxx = mxy = -inf; mnx = mny = inf; rep(i, n){ cin >> g[i].real() >> g[i].imag(); mxx = max((int)g[i].real(), mxx); mnx = min((int)g[i].real(), mnx); mxy = max((int)g[i].imag(), mxy); mny = min((int)g[i].imag(), mny); } mxx += 20 + GETA; mnx += -20 + GETA; mxy += 20 + GETA; mny += -20 + GETA; if(area2(g) < 0) reverse(all(g)); rep(i, n) draw(g[i], g[(i + 1) % n]); for(int i = mnx; i < mxx; i++) for(int j = mny; j < mxy; j++) if(!flag[i][j]){ rec(i, j, contains(g, P(i - GETA + 0.5, j - GETA + 0.5)) ? 1 : -1); } for(int i = mnx; i < mxx; i++) for(int j = mny; j < mxy; j++) if(flag[i][j] > 0) ans++; cout << ans << endl; for(int i = mnx; i < mxx; i++) for(int j = mny; j < mxy; j++) flag[i][j] = 0; } return 0; }