AOJ : 1242 - Area of Polygons

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1242
問題文中の図を見ていただければわかるかと思います。
多角形が入力されるので、「多角形の各線分が交わっているような正方形の数・多角形が完全内包している正方形の数」を数える問題です。

アルゴリズム

プログラムプロムナードで、とてもわかりやすく解説されているので、そちらを参考にしてください。
僕は、これとほぼ同じ方法で解きました。

http://www.ipsj.or.jp/07editj/promenade/4501.pdf

プログラム

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