QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#611477 | #9412. Stop the Castle | Komorebie | WA | 0ms | 3796kb | C++17 | 6.2kb | 2024-10-04 21:08:57 | 2024-10-04 21:08:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define PII pair<int, int>
#define pi acos(-1.0)
#define x first
#define y second
struct pair_hash {
template <class T1, class T2> size_t operator()(const pair<T1, T2>& p) const
{
auto h1 = hash<T1>{}(p.first);
auto h2 = hash<T2>{}(p.second);
return h1 ^ h2; // 哈希组合
}
};
struct seg {
PII a, b;
bool vertical() { return a.second == b.second; }
bool horizontal() { return a.first == b.first; }
};
void solve()
{
int n;
cin >> n;
vector<PII> a(n + 1);
unordered_set<PII, pair_hash> vis;
for (int i = 1; i <= n; i++) {
cin >> a[i].first >> a[i].second;
vis.insert({a[i].first, a[i].second});
}
int m;
cin >> m;
vector<PII> b(m + 1);
vector<seg> s;
for (int i = 1; i <= m; i++) {
cin >> b[i].first >> b[i].second;
vis.insert({b[i].first, b[i].second});
}
auto checkno = [&](PII a, PII b) {
auto [x1, y1] = a;
auto [x2, y2] = b;
if (x1 == x2 && abs(y1 - y2) == 1) return true;
if (y1 == y2 && abs(x1 - x2) == 1) return true;
return false;
};
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
auto [x1, y1] = a[i];
auto [x2, y2] = a[j];
bool have = false;
if (x1 != x2 && y1 != y2) continue;
if (checkno(a[i], a[j])) {
cout << -1 << endl;
return;
}
for (int k = 1; k <= m; k++) {
auto [x3, y3] = b[k];
if (x1 == x2) {
if (x3 == x1 && y3 >= min(y1, y2) && y3 <= max(y1, y2)) {
have = true;
break;
}
}
else {
if (y3 == y1 && x3 >= min(x1, x2) && x3 <= max(x1, x2)) {
have = true;
break;
}
}
}
if (!have) {
if (a[i].x < a[j].x || a[i].y < a[j].y)
s.push_back({a[i], a[j]});
else
s.push_back({a[j], a[i]});
}
}
}
// cout << s.size() << endl;
// for (int i = 0; i < s.size(); i++) {
// cerr << s[i].a.first << " " << s[i].a.second << " " << s[i].b.first << " " << s[i].b.second << "vertical:"<<s[i].vertical()<<endl;
// }
vector<int> ver, hor;
for (int i = 0; i < s.size(); i++) {
if (s[i].vertical())
ver.push_back(i);
else
hor.push_back(i);
}
auto check_cross = [&](seg a, seg b) {
return (a.a.x < b.a.x && a.b.x > b.a.x && a.a.y > b.a.y && a.a.y < b.b.y);
};
vector<vector<int>> G(s.size());
for (int i = 0; i < s.size(); i++) {
if (s[i].vertical()) {
for (int j = 0; j < s.size(); j++) {
if (s[j].horizontal()) {
if (check_cross(s[i], s[j])) G[i].push_back(j);
}
}
}
}
// cerr << "G" << endl;
// for (int i = 0; i < s.size(); i++) {
// for (int v : G[i]) {
// cerr << v << " ";
// }
// cerr << endl;
// }
// /*
// 3
// 2
// null
// null
// */
// cerr<<"endG"<<endl<<endl;
vector<bool> st;
vector<int> match(s.size(), -1);
auto find = [&](auto find, int u) -> bool {
for (int v : G[u]) {
if (!st[v]) {
st[v] = true;
if (match[v] == -1 || find(find, match[v])) {
match[v] = u;
// cerr<<"u:"<<u<<endl;
// cerr << v << " " << match[v] << endl;
return true;
}
}
}
return false;
};
for (int v : ver) {
st.assign(s.size(), false);
find(find, v);
}
vector<PII> ans;
vector<int> have_ans(s.size());
auto get_cross = [&](seg a, seg b) -> PII {
assert(a.horizontal());
// cerr << "fuck0" << endl;
vector<int> x, y;
x.push_back(a.a.first), x.push_back(a.b.first), x.push_back(b.a.first);
y.push_back(a.a.second), y.push_back(b.a.second), y.push_back(b.b.second);
sort(x.begin(), x.end());
sort(y.begin(), y.end());
return {x[1], y[1]};
// PII res = {x[1], y[1]};
// int axl = min(a.a.first, a.b.first), axh = max(a.a.first, a.b.first);
// int byl = min(b.a.second, b.b.second), byh = max(b.a.second, b.b.second);
// if (x[1] >= axl && x[1] <= axh && y[1] == a.a.second && x[1] == b.a.first && y[1] <= byh && y[1] >= byl) {
// return res;
// }
};
// cerr << "match" << endl;
// for (int i = 0; i < s.size(); i++) {
// cerr << match[i] << " \n"[i==s.size() - 1];
// }
for (int h : hor) {
if (match[h] != -1) {
ans.push_back(get_cross(s[h], s[match[h]]));
have_ans[h] = have_ans[match[h]] = 1;
}
}
// cout << ans.size() << endl;
// for (int i = 0; i < ans.size(); i++) {
// cout << ans[i].first << " " << ans[i].second << endl;
// }
auto get_point = [&](seg a) -> PII {
if (a.vertical()) {
return {a.a.first + 1, a.a.second};
}
else {
return {a.a.first, a.a.second + 1};
}
};
for (int i = 0; i < s.size(); i++) {
if (!have_ans[i]) ans.push_back(get_point(s[i]));
}
// for (int i = 0; i < s.size(); i++) {
// if (!st[i]) {
// ans.push_back(get_point(s[i]));
// }
// }
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++) {
cout << ans[i].first << " " << ans[i].second << endl;
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr);
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3796kb
input:
4 7 1 3 6 6 4 7 2 1 6 3 4 1 2 6 3 3 4 6 4 3 1 2 1 1 2 2 0 3 1 1 1 3 3 3 1 1 2 3 1 1 1 3 2 3 0
output:
2 4 6 2 3 0 1 2 3 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3628kb
input:
21 11 3 5 18 6 19 12 27 48 28 38 30 12 33 18 42 18 43 38 45 46 48 34 3 2 6 24 4 41 45 15 11 6 15 27 16 9 16 14 16 48 19 26 25 12 27 26 28 4 31 40 32 6 33 50 37 50 46 11 50 29 17 1 49 4 9 9 15 9 22 11 31 11 46 14 28 17 5 17 49 18 43 20 31 30 46 33 11 33 33 34 15 36 6 47 10 2 16 46 36 30 11 7 34 7 41 ...
output:
3 20 12 29 38 34 18 6 12 6 16 10 16 10 16 15 20 26 34 50 0 1 16 10 0 1 43 22 6 1 3 1 3 1 13 33 10 42 44 44 45 0 5 8 1 21 15 27 41 29 26 44 4 1 32 9 0 0 0 0 7 23 10 35 34 12 11 23 10 23 44 24 46 29 21 0 3 20 30 31 17 43 25 0 -1 3 16 36 17 39 25 7 6 5 5 8 9 6 4 7 3 3 10 2 11
result:
wrong answer Duplicated position (16, 10) (test case 2)