Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdlib>
- #include <iostream>
- #include <vector>
- #include <string>
- #include <cmath>
- #include <unordered_map>
- #include <stack>
- #include <cassert>
- #include <algorithm>
- #include <iomanip>
- #include <map>
- #include <queue>
- #include <set>
- #include <iostream>
- #include <climits>
- #include <vector>
- #include <cassert>
- #include <algorithm>
- #include <unordered_map>
- #include <map>
- #include <set>
- using namespace std;
- struct Seg {
- int to_comp;
- int l;
- int r;
- bool operator<(const Seg& seg) const {
- return to_comp < seg.to_comp;
- }
- };
- int64_t Go(const vector<Seg>& segs) {
- int64_t res = 0;
- auto comp = [](const Seg& s1, const Seg& s2) {
- return s1.l < s2.l;
- };
- set<Seg, decltype(comp)> st(comp);
- for (int i = 0; i < segs.size(); i++) {
- Seg cur = segs[i];
- for (auto& el : st) {
- if (cur.l >= el.r) {
- continue;
- }
- if (cur.r <= el.l) {
- continue;
- }
- if (cur.l < el.l) {
- res += el.l - cur.l;
- cur.l = el.l;
- }
- cur.l = min(cur.r, el.r);
- if (cur.l == cur.r) {
- break;
- }
- }
- res += cur.r - cur.l;
- st.insert(segs[i]);
- }
- return res;
- }
- int main() {
- freopen("intel.in", "r", stdin);
- freopen("intel.out", "w", stdout);
- ios_base::sync_with_stdio(0);
- cin.tie();
- int n;
- cin >> n;
- std::vector<pair<int, int>> points(n);
- std::vector<Seg> verticals;
- std::vector<Seg> hors;
- for (auto& el : points) {
- cin >> el.first >> el.second;
- }
- int64_t all = 0;
- for (int i = 0; i < n; i++) {
- int from = i;
- int to = (i - 1 + n) % n;
- all += abs(points[from].first - points[to].first) + abs(points[from].second - points[to].second);
- if (points[from].first == points[to].first) {
- int y1 = points[from].second;
- int y2 = points[to].second;
- verticals.push_back({points[from].first, min(y1, y2), max(y1, y2)});
- continue;
- }
- if (points[from].second == points[to].second) {
- int x1 = points[from].first;
- int x2 = points[to].first;
- hors.push_back({points[from].second, min(x1, x2), max(x1, x2)});
- continue;
- }
- assert(false);
- }
- sort(verticals.begin(), verticals.end());
- sort(hors.begin(), hors.end());
- int64_t sum = 0;
- sum += Go(verticals);
- reverse(verticals.begin(), verticals.end());
- sum += Go(verticals);
- sum += Go(hors);
- reverse(hors.begin(), hors.end());
- sum += Go(hors);
- cout << all - sum << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement