Advertisement
Guest User

Untitled

a guest
Oct 16th, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.79 KB | None | 0 0
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <vector>
  4. #include <string>
  5. #include <cmath>
  6. #include <unordered_map>
  7. #include <stack>
  8. #include <cassert>
  9. #include <algorithm>
  10. #include <iomanip>
  11. #include <map>
  12. #include <queue>
  13. #include <set>
  14.  
  15. #include <iostream>
  16. #include <climits>
  17. #include <vector>
  18. #include <cassert>
  19. #include <algorithm>
  20. #include <unordered_map>
  21. #include <map>
  22. #include <set>
  23.  
  24. using namespace std;
  25.  
  26. struct Seg {
  27.     int to_comp;
  28.     int l;
  29.     int r;
  30.  
  31.     bool operator<(const Seg& seg) const  {
  32.         return to_comp < seg.to_comp;
  33.     }
  34. };
  35.  
  36. int64_t Go(const vector<Seg>& segs) {
  37.     int64_t res = 0;
  38.     auto comp = [](const Seg& s1, const Seg& s2) {
  39.         return s1.l < s2.l;
  40.     };
  41.     set<Seg, decltype(comp)> st(comp);
  42.     for (int i = 0; i < segs.size(); i++) {
  43.         Seg cur = segs[i];
  44.         for (auto& el : st) {
  45.             if (cur.l >= el.r) {
  46.                 continue;
  47.             }
  48.             if (cur.r <= el.l) {
  49.                 continue;
  50.             }
  51.             if (cur.l < el.l) {
  52.                 res += el.l - cur.l;
  53.                 cur.l = el.l;
  54.             }
  55.             cur.l = min(cur.r, el.r);
  56.             if (cur.l == cur.r) {
  57.                 break;
  58.             }
  59.         }
  60.         res += cur.r - cur.l;
  61.         st.insert(segs[i]);
  62.     }
  63.     return res;
  64. }
  65.  
  66. int main() {
  67.     freopen("intel.in", "r", stdin);
  68.     freopen("intel.out", "w", stdout);
  69.  
  70.     ios_base::sync_with_stdio(0);
  71.     cin.tie();
  72.  
  73.     int n;
  74.     cin >> n;
  75.  
  76.     std::vector<pair<int, int>> points(n);
  77.  
  78.     std::vector<Seg> verticals;
  79.     std::vector<Seg> hors;
  80.  
  81.     for (auto& el : points) {
  82.         cin >> el.first >> el.second;
  83.     }
  84.  
  85.     int64_t all = 0;
  86.  
  87.     for (int i = 0; i < n; i++) {
  88.         int from = i;
  89.         int to = (i - 1 + n) % n;
  90.  
  91.         all += abs(points[from].first - points[to].first) + abs(points[from].second - points[to].second);
  92.  
  93.         if (points[from].first == points[to].first) {
  94.             int y1 = points[from].second;
  95.             int y2 = points[to].second;
  96.             verticals.push_back({points[from].first, min(y1, y2), max(y1, y2)});
  97.             continue;
  98.         }
  99.  
  100.         if (points[from].second == points[to].second) {
  101.             int x1 = points[from].first;
  102.             int x2 = points[to].first;
  103.             hors.push_back({points[from].second, min(x1, x2), max(x1, x2)});
  104.             continue;
  105.         }
  106.         assert(false);
  107.     }
  108.  
  109.     sort(verticals.begin(), verticals.end());
  110.     sort(hors.begin(), hors.end());
  111.  
  112.  
  113.     int64_t sum = 0;
  114.     sum += Go(verticals);
  115.     reverse(verticals.begin(), verticals.end());
  116.     sum += Go(verticals);
  117.  
  118.     sum += Go(hors);
  119.     reverse(hors.begin(), hors.end());
  120.     sum += Go(hors);
  121.  
  122.     cout << all - sum << endl;
  123.  
  124.  
  125.     return 0;
  126. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement