data_structure_algorithm/algorithm/code/missed_square.cpp at master · T-tssxuan/data_structure_algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <string>
#include <vector>
#include <istream>
#include <cmath>
#include <set>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <queue>
#include <bitset>
#include <sstream>

using namespace std;
using ll = long long;
struct Point {
    ll x;
    ll y;
};

ll MAX_VAL = 100000000;
int main() {
    int n;
    cin >> n;
    pair<ll, ll> lt, rb;
    cin >> lt.first >> lt.second >> rb.first >> rb.second;
    if (n == 1) {
        cout << lt.first << " " << lt.second << " " << rb.first << " " << rb.second << endl;
        return 0;
    }
    map<pair<ll, ll>, int> mm;
    vector<ll> xx;
    vector<ll> yy;
    pair<ll, ll> plt, prb;
    for (int i = 0; i < n - 1; ++i) {
        cin >> plt.first >> plt.second >> prb.first >> prb.second;
        xx.push_back(plt.first);
        xx.push_back(prb.first);
        yy.push_back(plt.second);
        yy.push_back(prb.second);
        if (mm.find(make_pair(plt.first, plt.second)) == mm.end()) {
            mm[make_pair(plt.first, plt.second)] = 0;
        }
        mm[make_pair(plt.first, plt.second)] += 1;
        if (mm.find(make_pair(plt.first, prb.second)) == mm.end()) {
            mm[make_pair(plt.first, prb.second)] = 0;
        }
        mm[make_pair(plt.first, prb.second)] += 1;
        if (mm.find(make_pair(prb.first, prb.second)) == mm.end()) {
            mm[make_pair(prb.first, prb.second)] = 0;
        }
        mm[make_pair(prb.first, prb.second)] += 1;
        if (mm.find(make_pair(prb.first, plt.second)) == mm.end()) {
            mm[make_pair(prb.first, plt.second)] = 0;
        }
        mm[make_pair(prb.first, plt.second)] += 1;
    }
    vector<pair<ll, ll>> candidate;
    for (auto ele : mm) {
        if ((ele.first.first == lt.first || ele.first.first == rb.first) &&
                (ele.first.second == lt.second || ele.first.second == rb.second)) {
            continue;
        } else {
            if (ele.second % 2 == 1) {
                candidate.push_back(ele.first);
            }
        }
    }
    int idx = 0;;
    pair<ll, ll> rlt, rrb;
    if (candidate.size() == 2) {
        if (candidate[0].first == candidate[1].first) {
            while (candidate[0].first == xx[idx]) { ++idx; }
            if (candidate[0].first > xx[idx]) {
                rlt.first = candidate[0].first;
                rlt.second = lt.second;
                rrb = rb;
            } else {
                rlt = lt;
                rrb.first = candidate[0].first;
                rrb.second = rb.second;
            }
        } else {
            while (candidate[0].second == yy[idx]) { ++idx; }
            if (candidate[0].second > yy[idx]) {
                rlt.first = lt.first;
                rlt.second = candidate[0].second;
                rrb = rb;
            } else {
                rlt = lt;
                rrb.first = rb.first;
                rrb.second = candidate[0].second;
            }
        }
    } else {
        rlt = rb;
        rrb = lt;
        for (auto ele : candidate) {
            rlt.first = min(rlt.first, ele.first);
            rlt.second = min(rlt.second, ele.second);
            rrb.first = max(rrb.first, ele.first);
            rrb.second = max(rrb.second, ele.second);
        }
    }
    cout << rlt.first << " " << rlt.second << " " << rrb.first << " " << rrb.second << endl;
    return 0;
}