QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#296711 | #692. Delete the Points | gubshig | WA | 736ms | 101572kb | C++14 | 2.0kb | 2024-01-03 14:23:29 | 2024-01-03 14:23:30 |
Judging History
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;
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));
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, 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);
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() && *itx <= 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() && *itx <= x2) flag = 0;
if(flag){
mx[p[i].x].insert(p[i].y);
my[p[i].y].insert(p[i].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: 100
Accepted
time: 1ms
memory: 3444kb
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: 1ms
memory: 3452kb
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: 3504kb
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: 0ms
memory: 3448kb
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: 3488kb
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: 3516kb
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
Wrong Answer
time: 736ms
memory: 101572kb
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 997371332 135791686 997371333 135791687 997371332 135791685 997371333 135791686 997371333 135791687 997371334 135791688 997371333 135791688 997371334 135791689 997371331 135791685 997371332 135791686 997371333 135791686 997371334 135791687 997371333 135791689 997371334 135791690 997371333 135791...
result:
wrong answer We have 4 point(s) in query 0