Advertisement

# Min Perimeter

Jun 5th, 2023
930
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4.
5. #define llong long long int
6. #define ldouble long double
7. #define Vector Point
8.
9. const ldouble EPS = 1e-10;
10. const ldouble INF = 9e18 + 5;
11.
12. int sign(ldouble x) {
13.     return fabsl(x) < EPS ? 0 : (x < 0 ? -1 : 1);
14. }
15.
16. template<typename T>
17. struct Point {
18.     T x, y;
19.
20.     Point(): x(0), y(0) {}
21.     Point(T x, T y): x(x), y(y) {}
22.
23.     Vector<T> operator -(Point<T> other) {
24.         return Vector<T>(x - other.x, y - other.y);
25.     }
26.
27.     T operator *(Vector<T> other) {
28.         return x * other.x + y * other.y;
29.     }
30.
31.     bool operator <(Point<T> const &other) const {
32.         if (x == other.x) return y < other.y;
33.         return x < other.x;
34.     }
35. };
36.
37. template<typename T>
38. ldouble abs(Vector<T> v) {
39.     return sqrtl(v * v);
40. }
41.
42. void merge(vector<Point<llong>> &left, vector<Point<llong>> &right, vector<Point<llong>> &all) {
43.     int i = 0, j = 0, k = 0, m = left.size(), n = right.size();
44.     while (i < m || j < n) {
45.         if (i >= m) all[k++] = right[j++];
46.         else if (j >= n) all[k++] = left[i++];
47.         else if (left[i].y <= right[j].y) all[k++] = left[i++];
48.         else all[k++] = right[j++];
49.     }
50. }
51.
52. ldouble min_perimeter(vector<Point<llong>> &points) {
53.     int n = points.size();
54.     if (n <= 2) return INF;
55.
56.     vector<Point<llong>> left(points.begin(), points.begin() + n / 2);
57.     vector<Point<llong>> right(points.begin() + n / 2, points.end());
58.
59.     llong middle = left.back().x;
60.     ldouble p = min(min_perimeter(left), min_perimeter(right));
61.     merge(left, right, points);
62.
63.     vector<Point<llong>> stripe;
64.     for (Point<llong> P: points) {
65.         llong dx = abs(P.x - middle);
66.         if (sign(dx - p) < 0) stripe.push_back(P);
67.     }
68.
69.     for (int i = 0; i < (int) stripe.size(); i++) {
70.         int idx = i + 1;
71.         bool done = false;
72.
73.         while (!done && idx < (int) stripe.size()) {
74.             llong dy = abs(stripe[idx].y - stripe[i].y);
75.             if (sign(dy - p) >= 0) done = true;
76.             else {
77.                 for (int j = i + 1; j < idx; j++) {
78.                     Vector<llong> u = stripe[j] - stripe[i];
79.                     Vector<llong> v = stripe[idx] - stripe[i];
80.                     Vector<llong> w = stripe[idx] - stripe[j];
81.                     p = min(p, abs(u) + abs(v) + abs(w));
82.                 }
83.
84.                 idx++;
85.             }
86.         }
87.     }
88.
89.     return p;
90. }
91.
92. int main() {
93.     ios_base::sync_with_stdio(false);
94.     cin.tie(NULL);
95.
96.     cout << setprecision(10) << fixed;
97.
98.     int n; cin >> n;
99.
100.     vector<Point<llong>> points(n);
101.     for (int i = 0; i < n; i++) {
102.         int x, y;
103.         cin >> x >> y;
104.         points[i] = Point<llong>(x, y);
105.     }
106.
107.     sort(points.begin(), points.end());
108.
109.     ldouble ans = min_perimeter(points);
110.     cout << ans << "\n";
111. }
Advertisement
Comments
• 119 days
1. Free RDP >> https://pastebin.com/30SgBHBy
Add Comment
Please, Sign In to add comment
Advertisement