题解 P2742 【[USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包】

ccviolett · 2020-08-03 17:21:50 · 题解

给出一种安全的求凸包的方法。

假定都会 Graham算法，在点排序以及跑凸包的过程中，容易出现与 x 或 y 坐标相同的点，此时会让人纠结处理方法，不当处理可能导致更复杂的问题出错。

解决方法为，给所有点统一旋转一个随机角度，求完凸包后再旋转回来即可。

/* Header {{{ */
#include <bits/stdc++.h>
using namespace std;

typedef long long readtype;
typedef long long var;
typedef long double let;

readtype read() {
  readtype a = 0, c = getchar(), s = 0;
  while (!isdigit(c)) s |= c == '-', c = getchar();
  while (isdigit(c)) a = a * 10 + c - 48, c = getchar();
  return s ? -a : a;
}

#ifdef LOCAL_LOGGER
#define logger(...) fprintf(stderr, __VA_ARGS__)
#define abortif(v, ...) if (v) {logger("Error in Line %d, Function '%s()'.\nInfo: ", __LINE__, __FUNCTION__); logger(__VA_ARGS__); exit(0);}
#else
#define logger(...);
#define abortif(v, ...);
#endif
/* }}} */

const int N = 1e5 + 1;
const let EPS = 1e-8;
const let Pi = acos(-1.0);

struct Point {
  let x, y;
  friend Point operator - (Point a, Point b) {
    return (Point) {a.x - b.x, a.y - b.y};
  }
  friend let Cdot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
  }
  friend let Times(Point a, Point b) {
    return a.x * b.y - a.y * b.x; 
  }
  let Dist() {
    return sqrt(x * x + y * y);
  }
  Point Rotate(let k) {
    Point kp = (Point) {sin(k), cos(k)};
    return (Point) {Times(*this, kp), Cdot(*this, kp)};
  }
};
typedef Point Vec;

int sign(let x) {
  if (x > EPS) return 1;
  if (x < -EPS) return -1;
  return 0;
}

bool CampByXY(Point a, Point b) {
  if (sign(a.x - b.x) == 0) return sign(a.y - b.y) < 0;
  return sign(a.x - b.x) < 0;
}

class Geometry {
  protected:
    int cnt, sta[N];
    Point tmp[N];

  public:
    void GetConvexHull(int n, Point *point, int &len, Point *res) {
      sort(point + 1, point + n + 1, CampByXY);
      sta[cnt = 1] = 1;
      for (int i = 2; i <= n; ++i) {
        while (cnt > 1 && Times(
              point[sta[cnt]] - point[sta[cnt - 1]],
              point[i] - point[sta[cnt]]
              ) < 0) cnt--;
        sta[++cnt] = i;
      }
      int down_hull_cnt = cnt;
      for (int i = n - 1; i >= 1; --i) {
        while (cnt > down_hull_cnt && Times(
              point[sta[cnt]] - point[sta[cnt - 1]],
              point[i] - point[sta[cnt]]
              ) < 0) cnt--;
        sta[++cnt] = i;
      }
      len = cnt;
      for (int i = 1; i <= len; ++i) 
        res[i] = point[sta[i]];
    }
    void GetCH(int n, Point *point, int &len, Point *res) {
      GetConvexHull(n, point, len, res);
    }
    void SafeGetCH(int n, Point *point, int &len, Point *res) {
      let angle = ((let) rand() / RAND_MAX) * Pi;
      for (int i = 1; i <= n; ++i) tmp[i] = point[i].Rotate(angle);
      GetConvexHull(n, tmp, len, res);
      for (int i = 1; i <= n; ++i) res[i] = res[i].Rotate(-angle);
    }
} geometry;

int n, m;
Point origin[N], hull[N];

int main() {
#ifndef ONLINE_JUDGE
  freopen("P2742.in", "r", stdin);
  freopen("P2742.out", "w", stdout);
#endif
#ifdef LOCAL_LOGGER
  freopen("P2742.log", "w", stderr);
#endif
  n = read();
  for (int i = 1; i <= n; ++i)
    scanf("%Lf%Lf", &origin[i].x, &origin[i].y);
  geometry.SafeGetCH(n, origin, m, hull);
  let res = (hull[1] - hull[m]).Dist();
  for (int i = 2; i <= m; ++i)
    res += (hull[i] - hull[i - 1]).Dist();
  printf("%.2Lf\n", res);
  return 0;
}

/* ==== Makefile ==== {{{
CompileAndRun:
    make Compile
    make Run

Compile:
    g++ -o P2742 P2742.cpp -g -Wall -DLOCAL_LOGGER

CompileUF:
    g++ -o P2742 P2742.cpp -g -Wall -DLOCAL_LOGGER -fsanitize=undefined

Run:
    ./P2742 < P2742.in > P2742.out
==================
}}} */