AOJ 2394: Longest Lane

この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 8 日目の記事です。

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2394

問題概要

頂点の凸と限らない多角形が与えられる。この多角形の内部または周上に完全に含まれる線分の長さの最大値を求めよ。

解法

多角形の頂点を反時計回りに とします。

実は、考える線分の候補は多角形の 頂点を通る線分のみとしてよいです。その 頂点を とすると、以下を調べる必要があります。

• 線分 が多角形の内部に含まれるか
• から、 と逆方向にどこまで伸ばせるか
• から、 と逆方向にどこまで伸ばせるか

多角形のそれぞれの辺と頂点について、線分を伸ばすことをどのように妨げるか調べます。辺については、その辺が線分 と端点以外で交わるかどうか調べ、交わる場合は交点と の位置関係を調べればよいです。

頂点については、前後の辺も含めて位置関係を調べなくてはならないため、複雑になります。結局、以下の判定に帰着します。

• 点 が与えられる。半直線 を点 を中心として まで反時計回りに回転させたとき、半直線が通過した領域に点 が与えられるか判定する。

これは と の外積の符号で場合分けすることで簡単な判定に帰着します。以下の実装では、関数 point_in_angle でこの判定を行っています。

実装

judge.u-aizu.ac.jp

#include <bits/stdc++.h>
using namespace std;
const double eps = 0.000001;
const double INF = 100000000;
int sign(double x){
  if (x > eps){
    return 1;
  } else if (x < -eps){
    return -1;
  } else {
    return 0;
  }
};
struct point{
  double x, y;
  point(){
  }
  point(double x, double y): x(x), y(y){
  }
  point operator +(point P){
    return point(x + P.x, y + P.y);
  }
  point operator -(point P){
    return point(x - P.x, y - P.y);
  }
};
double abs(point P){
  return sqrt(P.x * P.x + P.y * P.y);
}
double dist(point P, point Q){
  return abs(Q - P);
}
double dot(point P, point Q){
  return P.x * Q.x + P.y * Q.y;
}
double cross(point P, point Q){
  return P.x * Q.y - P.y * Q.x;
}
bool point_in_angle(point A, point B, point C, point P){
  B = B - A;
  C = C - A;
  P = P - A;
  if (abs(cross(B, P)) < eps && dot(B, P) > 0){
    return true;
  }
  if (abs(cross(C, P)) < eps && dot(C, P) > 0){
    return true;
  }
  if (abs(cross(B, C)) < eps){
    if (dot(B, C) > 0){
      return false;
    } else {
      return cross(B, P) > 0;
    }
  }
  if (cross(B, C) > 0){
    return cross(B, P) > 0 && cross(P, C) > 0;
  } else {
    return cross(B, P) > 0 || cross(P, C) > 0;
  }
}
struct line{
  point A, B;
  line(point A, point B): A(A), B(B){
  }
};
point vec(line L){
  return L.B - L.A;
}
bool segment_line_intersect(line L1, line L2){
  return sign(cross(L2.A - L1.A, vec(L1))) * sign(cross(L2.B - L1.A, vec(L1))) < 0;
}
bool segment_intersect(line L1, line L2){
  return segment_line_intersect(L1, L2) && segment_line_intersect(L2, L1);
}
int main(){
  cout << fixed << setprecision(10);
  int T = 0;
  while (true){
    int N;
    cin >> N;
    if (N == 0){
      break;
    }
    vector<point> P(N * 2);
    for (int i = 0; i < N; i++){
      cin >> P[i].x >> P[i].y;
    }
    for (int i = 0; i < N; i++){
      P[N + i] = P[i];
    }
    double ans = 0;
    for (int i = 1; i <= N; i++){
      for (int j = i + 1; j < i + N - 1; j++){
        double mn = -INF, mx = INF;
        bool ok = true;
        if (!point_in_angle(P[i], P[i + 1], P[i - 1], P[j])){
          ok = false;
        }
        if (!point_in_angle(P[i], P[i + 1], P[i - 1], P[i] + (P[i] - P[j]))){
          mn = 0;
        }
        if (!point_in_angle(P[j], P[j + 1], P[j - 1], P[i])){
          ok = false;
        }
        if (!point_in_angle(P[j], P[j + 1], P[j - 1], P[j] + (P[j] - P[i]))){
          mx = 1;
        }
        for (int k = 0; k < N; k++){
          if (k != i - 1 && k != i % N && k != (j - 1) % N && k != j % N){
            if (segment_line_intersect(line(P[i], P[j]), line(P[k], P[k + 1]))){
              double r = cross(P[k] - P[i], P[k + 1] - P[k]) / cross(P[j] - P[i], P[k + 1] - P[k]);
              if (r < eps){
                mn = max(mn, r);
              } else if (r > 1 - eps){
                mx = min(mx, r);
              } else {
                ok = false;
              }
            }
          }
        }
        for (int k = 0; k < N; k++){
          if (k != i % N && k != j % N){
            if (abs(cross(P[k] - P[i], P[j] - P[i])) < eps){
              if (!point_in_angle(P[k], P[k + 1], P[k + N - 1], P[k] + P[i] - P[j]) || !point_in_angle(P[k], P[k + 1], P[k + N - 1], P[k] + P[j] - P[i])){
                if (dot(P[k] - P[i], P[j] - P[i]) < 0){
                  mn = max(mn, -abs(P[k] - P[i]) / abs(P[j] - P[i]));
                } else if (dot(P[k] - P[j], P[j] - P[i]) > 0){
                  mx = min(mx, abs(P[k] - P[i]) / abs(P[j] - P[i]));
                } else {
                  ok = false;
                }
              }
            }
          }
        }
        if (ok){
          ans = max(ans, (mx - mn) * dist(P[i], P[j]));
        }
      }
    }
    cout << "Case " << T + 1 << ": " << ans << endl;
    T++;
  }
}