QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#326371#692. Delete the PointspjshwaWA 1ms3748kbC++171.8kb2024-02-12 23:03:592024-02-12 23:04:00

Judging History

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

  • [2024-02-12 23:04:00]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3748kb
  • [2024-02-12 23:03:59]
  • 提交

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();
}

Details

Tip: Click on the bar to expand more detailed information

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