QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#296724#692. Delete the PointsgubshigTL 1ms3564kbC++232.1kb2024-01-03 14:46:222024-01-03 14:46:24

Judging History

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

  • [2024-01-03 14:46:24]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3564kb
  • [2024-01-03 14:46:22]
  • 提交

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";
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3564kb

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

input:

4
0 0
1 2
2 1
4 4

output:

Yes
1 1 2 2
0 0 4 4

result:

ok OK

Test #3:

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

input:

4
1 2
3 2
2 1
2 3

output:

Yes
1 1 2 2
2 2 3 3

result:

ok OK

Test #4:

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

input:

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

output:

Yes
10 9 15 14
1 5 7 11
15 4 25 14

result:

ok OK

Test #5:

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

input:

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

output:

Yes
2 31 7 36
25 72 41 88
23 0 40 17
59 52 83 76
4 23 77 96

result:

ok OK

Test #6:

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

input:

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

output:

Yes
31 20 42 31
6 6 19 19
37 84 53 100
84 11 111 38
3 39 37 73

result:

ok OK

Test #7:

score: -100
Time Limit Exceeded

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:


result: