[PKU1113]Wall

这题求的就是一个凸包的周长再加上一个给定半径圆的周长（因为凸多边形的外角和=2pi）。可以作为凸包算法的模板。

这里用的是一种叫做“单调链法”的方法。先将所有点按照x坐标从小到大排序；然后从1到n线性扫描一遍，确定凸包的上壳；接着再从n到1扫描一边确定凸包的下壳。为了方便修改线段，所以可以将构成凸包的点按顺序存如一个栈中。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#include <cmath>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;

#define x first
#define y second
typedef pair<int, int> Point;
const double PI = acos(-1.0);
inline int sqr(const int x) { return x*x; }
inline bool operator<(const Point& lhs, const Point& rhs)
 { return lhs.x < rhs.x || (lhs.x == rhs.xx && lhs.y < rhs.y); }
inline int CrossProduct(const Point& A, const Point& B, const Point& C, const Point& D)
{
  const int x1 = B.x-A.x, y1 = B.y-A.y;
  const int x2 = D.x-C.x, y2 = D.y-C.y;
  return x1*y2-y1*x2;
}
class ConvexHull
{
  int top;
  Point stack[1000];
public:
  ConvexHull() : top(-1) { }
  void Add(const Point&);
  double Perimeter() const;
  void Init(const Point& first, const Point& second)
    { stack[++top] = first, stack[++top] = second; }
};
inline void ConvexHull::Add(const Point& x)
{
  while (top > 0 && CrossProduct(stack[top], x, stack[top], stack[top-1]) >= 0) --top;
  stack[++top] = x;
}
inline double ConvexHull::Perimeter() const
{
  double c = .0;
  for (int i = 0; i < top; ++i)
    c += sqrt(sqr(stack[i+1].x-stack[i].x)+sqr(stack[i+1].y-stack[i].y));
  return c;
}
int n, r;
Point a[1000];
ConvexHull Hull;
int main()
{
  ios::sync_with_stdio(false);
  cin >> n >> r;
  for (int i = 0; i < n; ++i)
    cin >> a[i].x >> a[i].y;

  sort(a, a+n);
  Hull.Init(a[0], a[1]);
  for (int i = 2; i < n; ++i)
    Hull.Add(a[i]);
  for (int i = n-1; i >= 0; --i)
    Hull.Add(a[i]);
  cout << fixed << setprecision(0) << Hull.Perimeter()+2*r*PI;
}

Comments