QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#296721#692. Delete the PointsgubshigWA 1ms3496kbC++172.1kb2024-01-03 14:40:402024-01-03 14:40:41

Judging History

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

  • [2024-01-03 14:40:41]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3496kb
  • [2024-01-03 14:40:40]
  • 提交

answer

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;

int n;
bool vis[3030];
pii p[3030];

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y;

    map<int, set<int>> mx, my;
    for(int i = 1; i <= n; i++){
        mx[p[i].x].insert(p[i].y);
        my[p[i].y].insert(p[i].x);
    }

    vector<array<int, 3>> v;
    for(int i = 1; i <= n; i++) for(int j = i + 1; j <= n; j++){
        int x1 = min(p[i].x, p[j].x), y1 = min(p[i].y, p[j].y);
        int w = max(max(p[i].x - x1, p[i].y - y1), max(p[j].x - x1, p[j].y - y1));
        v.push_back({w, i, j});
    }
    sort(all(v));

    vector<array<int, 4>> ans;
    for(auto &[w, i, j] : v){
        if(vis[i] || vis[j]) continue;

        int x1 = min(p[i].x, p[j].x), y1 = min(p[i].y, p[j].y);
        int x2 = x1 + w, y2 = y1 + w;
        mx[p[i].x].erase(p[i].y);
        my[p[i].y].erase(p[i].x);
        mx[p[j].x].erase(p[j].y);
        my[p[j].y].erase(p[j].x);

        bool flag = 1;
        auto itx = mx[x1].lower_bound(y1);
        if(!mx[x1].empty() && itx != mx[x1].end() && *itx <= y2) flag = 0;
        auto ity = my[y1].lower_bound(x1);
        if(!my[y1].empty() && ity != my[y1].end() && *ity <= x2) flag = 0;
        itx = mx[x2].lower_bound(y1);
        if(!mx[x2].empty() && itx != mx[x2].end() && *itx <= y2) flag = 0;
        ity = my[y2].lower_bound(x1);
        if(!my[y2].empty() && ity != my[y2].end() && *ity <= x2) flag = 0;
        if(flag){
            mx[p[i].x].insert(p[i].y);
            my[p[i].y].insert(p[i].x);
            mx[p[j].x].insert(p[j].y);
            my[p[j].y].insert(p[j].x);
        }
        else{
            vis[i] = 1;
            vis[j] = 1;
            ans.push_back({x1, y1, x2, y2});
        }
    }

    if(ans.size() == (n >> 1)){
        cout << "Yes\n";
        for(auto &[x1, y1, x2, y2] : ans){
            cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\n';
        }
    }
    else cout << "No";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3496kb

input:

4
1 1
2 2
5 5
6 6

output:

No

result:

wrong answer The participant does not have a solution