Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <stack>
- #define _USE_MATH_DEFINES
- #include <math.h>
- using namespace std;
- struct coor {
- long long int x, y;
- };
- long long int rotate(coor a, coor b, coor c) {
- return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
- }
- vector <coor> dots;
- int n;
- double l;
- int main()
- {
- cin >> n >> l;
- for (int i = 0; i < n; i++) {
- int a, b;
- cin >> a >> b;
- dots.push_back({ a, b });
- }
- int yy = 100000000, ind = -1;;
- for (int i = 0; i < n; i++) {
- if (dots[i].y < yy) {
- yy = dots[i].y;
- ind = i;
- }
- }
- coor beg = dots[ind];
- dots.erase(dots.begin() + ind);
- for (int i = 0; i < n - 1; i++) {
- dots[i].x = dots[i].x - beg.x;
- dots[i].y = dots[i].y - beg.y;
- }
- beg.x = 0; beg.y = 0;
- sort(dots.begin(), dots.end(), [](coor a, coor b) {
- if (a.x * b.y == b.x * a.y) {
- if (a.y == b.y) {
- if (a.x < b.x) {
- return true;
- }
- else {
- return false;
- }
- }
- else {
- if (a.y < b.y) {
- return true;
- }
- else {
- return false;
- }
- }
- }
- else {
- return (a.x * b.y > b.x * a.y);
- }
- });
- vector <coor> aga;
- aga.push_back(beg);
- aga.push_back(dots[0]);
- for (int i = 1; i < n - 1; i++) {
- while (rotate(aga[aga.size() - 1], dots[i], aga[aga.size() - 2]) < 0) {
- aga.erase(aga.end() - 1);
- }
- aga.push_back(dots[i]);
- }
- while (rotate(aga[aga.size() - 1], beg, aga[aga.size() - 2]) < 0) {
- aga.erase(aga.end() - 1);
- }
- double summ = 0;
- for (int i = 1; i < aga.size(); i++) {
- summ += sqrt(pow(aga[i].x - aga[i - 1].x, 2) + pow(aga[i].y - aga[i - 1].y, 2));
- }
- summ += sqrt(pow(beg.x - aga[aga.size() - 1].x, 2) + pow(beg.y - aga[aga.size() - 1].y, 2));
- summ += 2 * M_PI * l;
- cout << (int) (summ + 0.5);
- }
Advertisement
Add Comment
Please, Sign In to add comment