Convex Hull

From EOJ Wiki
Revision as of 00:52, 11 March 2018 by Ultmaster (talk | contribs) (Created page with "<syntaxhighlight lang='cpp'> 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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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);
    }
}