Convex Hull
Jump to navigation
Jump to search
ld area2(PT a, PT b, PT c) { return cross(a,b) + cross(b,c) + cross(c,a); }
#ifdef REMOVE_REDUNDANT
// return true if point b is between points a and c
bool between(const PT &a, const PT &b, const PT &c) {
return (dcmp(area2(a, b, c)) == 0 &&
dcmp((a.x - b.x) * (c.x - b.x)) <= 0 &&
dcmp((a.y - b.y) * (c.y - b.y)) <= 0);
}
#endif
void convex_hull(VPT &pts) {
sort(pts.begin(), pts.end());
pts.erase(unique(pts.begin(), pts.end()), pts.end());
VPT up, dn;
for (int i = 0; i < (int) pts.size(); i++) {
while (up.size() > 1 && dcmp(area2(up[up.size() - 2], up.back(), pts[i])) >= 0)
up.pop_back();
while (dn.size() > 1 && dcmp(area2(dn[dn.size() - 2], dn.back(), pts[i])) <= 0)
dn.pop_back();
up.push_back(pts[i]);
dn.push_back(pts[i]);
}
pts = dn;
for (int i = (int) up.size() - 2; i >= 1; i--) pts.push_back(up[i]);
#ifdef REMOVE_REDUNDANT
if (pts.size() <= 2) return;
dn.clear();
dn.push_back(pts[0]);
dn.push_back(pts[1]);
for (int i = 2; i < (int) pts.size(); i++) {
if (between(dn[dn.size() - 2], dn[dn.size() - 1], pts[i])) dn.pop_back();
dn.push_back(pts[i]);
}
if (dn.size() >= 3 && between(dn.back(), dn[0], dn[1])) {
dn[0] = dn.back();
dn.pop_back();
}
pts = dn;
#endif
}
int main() {
int n, l;
while (cin >> n >> l) {
VPT v(n);
for (int i = 0; i < n; ++i)
cin >> v[i];
convex_hull(v);
int m = v.size();
ld ans = 0;
for (int i = 0; i < m; ++i)
ans += DistanceBetweenPoints(v[i], v[(i+1)%m]);
ans += PI * l * 2;
printf("%.f\n", ans);
}
}