Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <iomanip>
- #include <algorithm>
- using namespace std;
- struct Vect
- {
- long double x, y;
- Vect(long double _x = 0, long double _y = 0) : x(_x), y(_y){}
- Vect(const Vect &p) : x(p.x), y(p.y){}
- Vect operator +(const Vect &other) const
- {
- return {x + other.x, y + other.y};
- }
- Vect operator -(const Vect &other) const
- {
- return {x - other.x, y - other.y};
- }
- long double operator *(const Vect &other) const
- {
- return x * other.x + y * other.y;
- }
- long double operator %(const Vect &other) const
- {
- return x * other.y - y * other.x;
- }
- };
- istream& operator >> (istream &in, Vect &v)
- {
- in >> v.x >> v.y;
- return in;
- }
- ostream& operator << (ostream &out, const Vect &v)
- {
- out << v.x << " " << v.y;
- return out;
- }
- struct Line
- {
- Vect p, d;
- Line(Vect &f, Vect &s) : p(f), d(s - f){}
- };
- bool is_in(Vect &A, Vect &B, Vect &C)
- {
- return (A.x - C.x) * (B.x - C.x) <= 0 && (A.y - C.y) * (B.y - C.y) <= 0 && (C - A) % (C - B) == 0;
- }
- vector <Vect> points;
- int ind_left = 0;
- long double Distance(Vect a)
- {
- return sqrt(a.x * a.x + a.y * a.y);
- }
- bool cmp(Vect a, Vect b)
- {
- return (a - points[ind_left]) % (b - points[ind_left]) > 0 ||
- ((a - points[ind_left]) % (b - points[ind_left]) == 0 &&
- Distance((a - points[ind_left])) < Distance((b - points[ind_left])));
- }
- int main()
- {
- int n;
- cin >> n;
- vector <pair<long double, long double>> directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
- for (int i = 0; i < n; i++)
- {
- Vect t, d;
- cin >> t;
- points.push_back(t);
- for (auto dir: directions) {
- d.x = t.x + dir.first;
- d.y = t.y + dir.second;
- points.push_back(d);
- }
- }
- n = points.size();
- for (int i = 0; i < n; i++) /// ----- find min x and min y point
- {
- if (points[i].x < points[ind_left].x ||
- (points[i].x == points[ind_left].x && points[i].y < points[ind_left].y))
- {
- ind_left = i;
- }
- } /// --- end
- // for (int i = 0; i < n; i++){
- // cout << points[i].x << ' ' << points[i].y << '\n';
- // }
- vector <Vect> convex_hull;
- convex_hull.push_back(points[ind_left]);
- vector <Vect> sorted; /// without left point !
- for (int i = 0; i < n; i++)
- {
- if (i != ind_left)
- {
- sorted.push_back(points[i]);
- }
- }
- sort(sorted.begin(), sorted.end(), cmp);
- if (sorted.size() > 0){
- convex_hull.push_back(sorted[0]);
- }
- for (int i = 1; i < sorted.size(); i++) /// take points
- {
- Vect last_vec = convex_hull.back();
- //convex_hull.pop_back();
- Vect prev_last = convex_hull[convex_hull.size() - 2];
- //convex_hull.pop_back();
- while (convex_hull.size() > 1 && (last_vec - prev_last) % (sorted[i] - last_vec) <= 0)
- {
- convex_hull.pop_back();
- last_vec = prev_last;
- prev_last = convex_hull[convex_hull.size() - 2];
- //prev_last = convex_hull.back();
- //convex_hull.pop_back();
- }
- //convex_hull.push_back(prev_last);
- //if ((last_vec - prev_last) % (sorted[i] - last_vec) > 0){
- // convex_hull.push_back(last_vec);
- //}
- convex_hull.push_back(sorted[i]);
- }
- long double P = 0;
- Vect last_vec = points[ind_left];
- while (!convex_hull.empty()) {
- long double distx = abs(convex_hull.back().x - last_vec.x);
- long double disty = abs(convex_hull.back().y - last_vec.y);
- P += abs(distx - disty);
- P += Distance(Vect(min(distx, disty), min(distx, disty)));
- if (convex_hull.size() > 1) {
- last_vec = convex_hull.back();
- convex_hull.pop_back();
- } else {
- convex_hull.pop_back();
- }
- }
- cout << setprecision(20) << P;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement