Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _USE_MATH_DEFINES
- #include <iostream>
- #include <vector>
- #include <utility>
- #include <climits>
- #include <cmath>
- using namespace std;
- double dist(pair<int, int> a, pair<int, int> b)
- {
- long long int x = (a.first - b.first);
- long long int y = (a.second - b.second);
- return sqrt(x * x + y * y);
- }
- int main()
- {
- int N;
- cin >> N;
- vector<pair<int, int>> dots;
- int min_x = 100000000;
- int max_x = -100000000;
- int min_y = 100000000;
- int max_y = -100000000;
- for (int i = 0; i < N; i++) {
- int x, y;
- cin >> x >> y;
- dots.push_back(pair<int, int>{x, y});
- if (x < min_x) {
- min_x = x;
- } else if (x > max_x) {
- max_x = x;
- }
- if (y < min_y) {
- min_y = y;
- } else if (y > max_y) {
- max_y = y;
- }
- }
- vector<pair<int, int>> coords = {{min_x - 1, min_y - 1},
- {min_x - 1, max_y + 1},
- {max_x + 1, max_y + 1},
- {max_x + 1, min_y - 1}};
- vector<pair<int, int>> external = {{INT_MAX, INT_MAX},
- {INT_MAX, INT_MAX},
- {INT_MAX, INT_MAX},
- {INT_MAX, INT_MAX}};
- for (size_t i = 0; i < dots.size(); i++) {
- for (int j = 0; j < 4; j++) {
- if (dist(coords[j], dots[i]) < dist(coords[j], external[j])) {
- external[j] = dots[i];
- }
- }
- }
- double P = (max_x + 1 - min_x + 1) * 2 + (max_y + 1 - min_y + 1) * 2;
- for (int i = 0; i < 4; i++) {
- int a = abs(coords[i].first - external[i].first);
- int b = abs(coords[i].second - external[i].second);
- P = P - 2 * (a + b - 1) + (a + b - 1) * sqrt(2);
- }
- cout << P;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement