QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#296721 | #692. Delete the Points | gubshig | WA | 1ms | 3496kb | C++17 | 2.1kb | 2024-01-03 14:40:40 | 2024-01-03 14:40:41 |
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;
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