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;
}