QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#326371 | #692. Delete the Points | pjshwa | WA | 1ms | 3748kb | C++17 | 1.8kb | 2024-02-12 23:03:59 | 2024-02-12 23:04:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
void fast_io() {
cin.tie(nullptr)->sync_with_stdio(false);
}
void solve() {
int N; cin >> N;
map<int, vector<int>> F;
for (int i = 0; i < N; ++i) {
int x, y; cin >> x >> y;
F[y].push_back(x);
}
vector<tuple<int, int, int, int>> ans;
vector<pair<int, int>> R;
auto sq_len = [&](int x1, int y1, int x2, int y2) {
int maxx = max(x1, x2), minx = min(x1, x2);
int maxy = max(y1, y2), miny = min(y1, y2);
int len = max(maxx - minx, maxy - miny);
return len;
};
auto add_point = [&](int x1, int y1, int x2, int y2) {
int len = sq_len(x1, y1, x2, y2);
int maxx = max(x1, x2), maxy = max(y1, y2);
ans.emplace_back(maxx - len, maxy - len, maxx, maxy);
};
vector<pii> cur;
int px = -1, py = -1;
for (auto& [y, xv] : F) {
for (int x : xv) cur.emplace_back(x, y);
sort(cur.begin(), cur.end());
while (cur.size() >= 2) {
auto [x1, y1] = cur.back(); cur.pop_back();
auto [x2, y2] = cur.back(); cur.pop_back();
if (px != -1 && x2 <= px && px <= x1) {
int plen = sq_len(px, py, x1, y1);
int nlen = sq_len(x2, y2, x1, y1);
if (plen < nlen) {
add_point(px, py, x1, y1);
px = -1, py = -1;
cur.emplace_back(x2, y2);
}
else add_point(x2, y2, x1, y1);
}
}
if (cur.empty()) continue;
auto [xr, yr] = cur.back(); cur.pop_back();
if (px == -1) px = xr, py = yr;
else {
add_point(px, py, xr, yr);
px = -1, py = -1;
}
}
cout << "Yes\n";
for (auto [x1, y1, x2, y2] : ans) {
cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
}
}
int main() {
fast_io();
int t = 1;
// cin >> t;
while (t--) solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3496kb
input:
4 1 1 2 2 5 5 6 6
output:
Yes 1 1 2 2 5 5 6 6
result:
ok OK
Test #2:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
4 0 0 1 2 2 1 4 4
output:
Yes 0 -1 2 1 1 1 4 4
result:
ok OK
Test #3:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
4 1 2 3 2 2 1 2 3
output:
Yes 2 1 3 2 1 2 2 3
result:
ok OK
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3620kb
input:
6 12 9 1 5 10 14 20 14 15 4 7 9
output:
Yes 1 -9 15 5
result:
wrong answer Unexpected EOF