ei1333's page

凸多角形の直径

説明

凸多角形の直径を求める。ここで凸多角形の直径とは最も遠い頂点間の距離である。

最遠点対は凸包上の $2$ 点のいずれかなので, ある点集合が与えられたとするとその凸包をとって直径を求めることで最遠点対を求めることができる。

計算量

$O(N)$

実装例

double Convex_Diameter(Polygon& p){
  int n = p.size();
  int is = 0, js = 0;
  for(int i = 1; i < n; i++){
    if(p[i].y > p[is].y) is = i;
    if(p[i].y < p[js].y) js = i;
  }
  double maxdis = (p[is] - p[js]).norm();
  
  int maxi, maxj, i, j;
  i = maxi = is;
  j = maxj = js;
  do {
    if(cross(p[(i + 1) % n] - p[i], p[(j + 1) % n] - p[j]) >= 0){
      j = (j + 1) % n;
    } else {
      i = (i + 1) % n;
    }
    if((p[i] - p[j]).norm() > maxdis){
      maxdis = (p[i] - p[j]).norm();
      maxi = i; maxj = j;
    }
  }  while (i != is || j != js);
  return maxdis;
}