PKU : 2954 - Triangle

幾何

問題概要

http://poj.org/problem?id=2954

二次元平面上に, 三角形を構成する三つの点が与えられます.
この三角形の内部には, いくつの格子点が存在するでしょうか.

アルゴリズム

三角形に交わるような, y座標が整数となる水平な直線を引く.
このとき, 三角形と直線とで, 2つの交差点ができる.(三角形の上端と下端は除く)
この2つの交差点の間にある, 格子点の数を全て数えあげれば, 答えを出すことができる.

プログラム

幾何のライブラリは, スパゲッティソース(http://www.prefield.com/algorithm/index.html)のコードを使わせていただいています.
一部, 変更しているところもあります.

static const double EPS = 1e-8;
typedef complex<double> P;

#define MAX 99999

double cross(P a,P b){
  return imag(conj(a)*b);
}

bool intersectLS(int y,P c,P d){
  return min(c.imag(),d.imag()) <= y && y <= max(c.imag(),d.imag());
}

P crosspoint(P a,P b,P c,P d){
  double A = cross(b - a, d - c);
  double B = cross(b - a, b - c);
  return c + B / A * (d - c);
}

int main(void){
  while(1){
    bool endFlg = true;
    P p[3];
    int minY=MAX,maxY=-MAX;
    rep(i,3){
      scanf("%lf%lf",&p[i].real(),&p[i].imag());
      minY = min(minY,(int)p[i].imag());
      maxY = max(maxY,(int)p[i].imag());
      if(p[i].real() != 0 || p[i].imag() != 0) endFlg = false;
    }
    if(endFlg) break;

    int ans = 0;
    for(int y=minY+1;y<maxY;y++){
      int left=MAX,right=-MAX;
      for(int i=0;i<3;i++){
        if(!intersectLS(y,p[i],p[(i+1)%3])) continue;
        P cr = crosspoint(P(-MAX,y),P(MAX,y),p[i],p[(i+1)%3]);

        int tmp = ceil(cr.real()+EPS);
        if(left > tmp) left = tmp;
        tmp = floor(cr.real()-EPS);
        if(right < tmp) right = tmp;
      }
      ans += right - left + 1;
    }

    printf("%d\n",ans);
  }
}