[2017 ACM-ICPC WF] Airport Construction

题意:

给定一个简单多边形(不一定凸),求完全位于该简单多边形边界及内部的最长线段的长度。点数200,坐标为整数且绝对值不超过1e6。

题解:

可以证明存在一条最优的的线段经过多边形的两个顶点。假设最优线段不经过顶点,则总可以向某一方向平移最优线段使得其长度不减少,直到碰到某一个顶点。然后绕着该顶点旋转,总有一个旋转方向使得线段的长度不会减小,直到线段碰到另一个顶点为止。

然后算法就很显然了:枚举多边形的两个顶点并将其延长,并用多边形将直线打散成若干条线段,删去在多边形外的线段,并将多边形内的连续线段合并,取最大的即可。枚举多边形两个顶点是\(O(n^2)\)的,打散成线段是\(O(n)\)的,判断线段是否在多边形内可以取中点,转化为点是否在多边形内,复杂度为\(O(n)\)。总复杂度为\(O(n^4)\),写的时候代码过于粗糙T了一发 QAQ

本题复杂度可以降到\(O(n^3)\),但具体做法还没仔细研究…

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define Rep(i, n) for (int i = 1; i <=(n); i++)
#define range(x) begin(x), end(x)

typedef complex<double> pt, vec;
typedef pair<pt, pt> seg;

const double EPS = 1e-8;
int fcmp(double a, double b = 0.0) {
  if (fabs(a - b) < EPS) return 0;
  return a < b ? -1 : 1;
}

double operator * (pt a, pt b) {
  return a.real() * b.imag() - a.imag() * b.real();
}

double operator , (pt a, pt b) {
  return a.real() * b.real() + a.imag() * b.imag();
}

inline bool ptOnSeg(pt p, seg s){
    vec v1 = s.first - p, v2 = s.second - p;
    return fcmp((v1, v2)) <= 0 && fcmp(v1 * v2) == 0;
}

inline pt getIntersection(pt P, vec v, pt Q, vec w) {
    return P + v * (w*(P-Q)/(v*w));
}

// -1 outside the polygon
// 0  on the border of the polygon
// 1  inside the polygon
int ptOnPoly(pt p, pt* poly, int n){
//  fprintf(stderr, "(%.7f, %.7f)\n", p);
    int wn = 0;
    for (int i = 0; i < n; i++){
        if (ptOnSeg(p, {poly[i], poly[i+1]})) return 0;
        int d1 = fcmp(poly[i].imag() - p.imag()), 
            d2 = fcmp(poly[i+1].imag() - p.imag()),
            k = fcmp((poly[i+1] - poly[i])*(p - poly[i]));
        if (k > 0 && d1 <= 0 && d2 > 0) wn++;
        if (k < 0 && d2 <= 0 && d1 > 0) wn--;
    }
    return wn ? 1 : -1;
}

istream& operator >> (istream& lhs, pt& rhs){
  double x, y;
  lhs >> x >> y;
  rhs = {x, y};
  return lhs;
}

int n;
vector<pt> poly;
double ans = 0.0;

void attempt(pt a, pt b) {
  vector<pt> points;
  rep (i, n) 
    if (fcmp((b-a)*(poly[i]-a)) * fcmp((b-a)*(poly[i+1]-a)) <= 0) {
      auto vec1 = b-a, vec2 = poly[i+1] - poly[i];
      if (fcmp(vec1 * vec2) == 0) {
        points.push_back(poly[i]);
        points.push_back(poly[i+1]);
      } else {
        points.push_back(getIntersection(a, b-a, poly[i], poly[i+1]-poly[i]));
      }
    }
  sort(range(points), [] (pt a, pt b) {
        return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag());
      });
  points.resize(unique(range(points), [] (pt a, pt b) {
          return fcmp(a.real(), b.real()) == 0 && fcmp(a.imag(), b.imag()) == 0;
        }) - points.begin());
  double cur = 0.0;
  assert(points.size() > 1);
  for (int i = 1; i < points.size(); i++) {
    if (ptOnPoly((points[i]+points[i-1]) / 2.0, poly.data(), n) >= 0) {
      cur += abs(points[i] - points[i-1]);
    } else {
      cur = 0.0;
      if (abs(points.back() - points[i]) <= ans) return;
    }
    ans = max(ans, cur);
  }
}

int main() {
  cin >> n; poly.resize(n);
  rep (i, n) cin >> poly[i];
  poly.push_back(poly[0]);
  rep (i, n) {
    rep (j, i) {
      attempt(poly[i], poly[j]);
    }
  }
  printf("%.8f\n", ans);
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注