Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- // @author: Danielto1404
- #define c_boost std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr)
- using namespace std;
- struct point {
- int x, y;
- };
- double size(point a, point b) {
- int hyp_cnt = min(abs(a.x - b.x), abs(a.y - b.y));
- int max_size = max(abs(a.x - b.x), abs(a.y - b.y));
- return sqrt(2) * hyp_cnt + (max_size - hyp_cnt);
- }
- bool negative(point a, point b, point c) {
- return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
- }
- bool positive(point a, point b, point c) {
- return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
- }
- void find_min_shell(vector<point> &points) {
- if (points.size() == 1) return;
- sort(points.begin(), points.end(), [](point a, point b) {
- return a.x < b.x || (a.x == b.x && a.y < b.y);
- });
- point left = points.front(), right = points.back();
- vector<point> up, down;
- up.push_back(left);
- down.push_back(left);
- for (int i = 1; i < points.size(); ++i) {
- if (i == points.size() - 1 || negative(left, points[i], right)) {
- while (up.size() >= 2 && !negative(up[up.size() - 2], up.back(), points[i]))
- up.pop_back();
- up.push_back(points[i]);
- }
- if (i == points.size() - 1 || positive(left, points[i], right)) {
- while (down.size() >= 2 && !positive(down[down.size() - 2], down.back(), points[i]))
- down.pop_back();
- down.push_back(points[i]);
- }
- }
- points.clear();
- for (const point p : up)
- points.push_back(p);
- for (int i = (int) down.size() - 2; i > 0; --i)
- points.push_back(down[i]);
- }
- int main() {
- c_boost;
- int n, x, y;
- cin >> n;
- vector<point> points;
- for (int i = 0; i < n; ++i) {
- cin >> x >> y;
- points.push_back({x + 1, y});
- points.push_back({x - 1, y});
- points.push_back({x, y + 1});
- points.push_back({x, y - 1});
- }
- find_min_shell(points);
- double perimeter = 0;
- for (int i = 0; i < points.size() - 1; ++i) {
- perimeter += size(points[i], points[i + 1]);
- }
- perimeter += size(points.back(), points.front());
- cout << perimeter;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement