AOJ : 1242 - Area of Polygons
問題概要
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1242
問題文中の図を見ていただければわかるかと思います。
多角形が入力されるので、「多角形の各線分が交わっているような正方形の数・多角形が完全内包している正方形の数」を数える問題です。
アルゴリズム
プログラムプロムナードで、とてもわかりやすく解説されているので、そちらを参考にしてください。
僕は、これとほぼ同じ方法で解きました。
プログラム
#define INF 999999 typedef complex<double> P; int n; P t[102]; bool flg[5000]; //スパゲッティソースより引用 //外積計算 double cross(P a, P b) {省略} //スパゲッティソースより引用 //abとcdの交点計算 P crosspoint(P a,P b,P c,P d){省略} //Y座標がyである水平線と, 多角形との交点を列挙する vector<double> getCrossPoint(double y){ vector<double> v; rep(i,n){ if(t[i].imag() < y && y < t[(i+1)%n].imag() || t[(i+1)%n].imag() < y && y < t[i].imag()){ P p = crosspoint(P(-INF,y),P(INF,y),t[i],t[(i+1)%n]); v.push_back(p.real()); } } sort(v.begin(),v.end()); return v; } int main(void){ while(scanf("%d",&n),n){ int hy = -INF, ly = INF; rep(i,n){ scanf("%lf%lf",&t[i].real(),&t[i].imag()); t[i].real() += 2000; //マイナスにならないように平行移動 t[i].imag() += 2000; hy = max(hy,(int)t[i].imag()); ly = min(ly,(int)t[i].imag()); } int res = 0; REP(i,ly,hy){ memset(flg,0,sizeof(flg)); vector<double> v1 = getCrossPoint(i+EPS); vector<double> v2 = getCrossPoint(i+1-EPS); for(int i=0;i<v1.size();i+=2){ int from = floor(min(v1[i],v2[i])); int to = ceil(max(v1[i+1],v2[i+1])); for(int j=from;j<to;j++){ if(!flg[j]){ res++; flg[j] = true; } } } } printf("%d\n",res); } }