QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#326378#692. Delete the PointspjshwaWA 1ms3712kbC++171.8kb2024-02-12 23:13:042024-02-12 23:13:06

Judging History

你现在查看的是最新测评结果

  • [2024-02-12 23:13:06]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3712kb
  • [2024-02-12 23:13:04]
  • 提交

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 minx = min(x1, px), maxy = max(y1, py);
        ans.emplace_back(minx, maxy - plen, minx + plen, maxy);

        px = -1, py = -1;
        cur.emplace_back(x2, y2);
      }
      else add_point(x1, y1, x2, y2);
    }

    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: 3544kb

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: 3540kb

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: 3580kb

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: 0
Accepted
time: 0ms
memory: 3620kb

input:

6
12 9
1 5
10 14
20 14
15 4
7 9

output:

Yes
1 -9 15 5
7 4 12 9
10 4 20 14

result:

ok OK

Test #5:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

10
39 72
59 52
23 17
2 31
30 0
25 88
2 36
61 23
4 96
59 76

output:

Yes
13 0 30 17
2 -28 61 31
2 -5 59 52
39 56 59 76
4 75 25 96

result:

ok OK

Test #6:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

10
53 95
37 51
84 11
3 39
31 20
37 84
42 27
95 38
6 6
16 19

output:

Yes
6 -67 84 11
16 5 31 20
42 -15 95 38
3 17 37 51
37 79 53 95

result:

ok OK

Test #7:

score: -100
Wrong Answer
time: 1ms
memory: 3712kb

input:

3000
997371332 135791687
997371332 135791686
997371332 135791685
997371333 135791685
997371333 135791687
997371334 135791687
997371333 135791688
997371331 135791686
997371333 135791689
997371334 135791686
997371334 135791689
997371333 135791684
997371332 135791689
997371331 135791685
997371334 13579...

output:

Yes
997371329 135791653 997371330 135791654
997371328 135791653 997371329 135791654
997371324 135791653 997371325 135791654
997371328 135791653 997371330 135791655
997371325 135791653 997371327 135791655
997371331 135791655 997371332 135791656
997371329 135791655 997371330 135791656
997371327 135791...

result:

wrong answer We have 3 point(s) in query 72