Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct Point {
- long long x, y;
- Point() {}
- Point(long long _x, long long _y) : x(_x), y(_y) {}
- bool operator<(Point &b) {
- return (this->x == b.x ? this->y < b.y : this->x < b.x);
- }
- };
- bool rightturn(Point pA, Point pB, Point pC) {
- return (long long)pA.x * (pB.y - pC.y) + pB.x * (pC.y - pA.y) + pC.x * (pA.y - pB.y) < 0;
- }
- bool leftturn(Point pA, Point pB, Point pC) {
- return (long long)pA.x * (pB.y - pC.y) + pB.x * (pC.y - pA.y) + pC.x * (pA.y - pB.y) > 0;
- }
- void ch(vector <Point> &in) {
- sort(in.begin(), in.end());
- Point first_point = in[0];
- Point second_point = in.back();
- vector <Point> convexhullup, convexhulldown;
- convexhullup.push_back(first_point);
- convexhulldown.push_back(first_point);
- for (long long i = 1; i < in.size(); ++i) {
- if (i == in.size() - 1 || rightturn(first_point, in[i], second_point)) {
- while (convexhullup.size() >= 2 && !rightturn(convexhullup[convexhullup.size() - 2], convexhullup[convexhullup.size() - 1], in[i])) convexhullup.pop_back();
- convexhullup.push_back(in[i]);
- }
- if (i == in.size() - 1 || leftturn(first_point, in[i], second_point)) {
- while (convexhulldown.size() >= 2 && !leftturn(convexhulldown[convexhulldown.size() - 2], convexhulldown[convexhulldown.size() - 1], in[i])) convexhulldown.pop_back();
- convexhulldown.push_back(in[i]);
- }
- }
- in.clear();
- for (long long i = 0; i < convexhullup.size(); ++i) in.push_back(convexhullup[i]);
- for (long long i = convexhulldown.size() - 2; i > 0; --i) in.push_back(convexhulldown[i]);
- }
- int main() {
- long long a, b;
- int n, l;
- cin >> n >> l;
- vector < Point > v;
- for (long long i = 0; i < n; i++) {
- cin >> a >> b;
- v.push_back({a, b});
- }
- ch(v);
- double p = 0.0;
- for (int i = 0; i < v.size(); i++) {
- if (!i) {
- p += sqrtl((v[0].x - v.back().x) * (v[0].x - v.back().x) + (v[0].y - v.back().y) * (v[0].y - v.back().y));
- } else {
- p += sqrtl((v[i].x - v[i - 1].x) * (v[i].x - v[i - 1].x) + (v[i].y - v[i - 1].y) * (v[i].y - v[i - 1].y));
- }
- }
- p += 2 * acosl(-1) * l;
- cout << fixed << setprecision(12) << p;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement