QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#603870 | #7800. Every Queen | surgutti# | WA | 0ms | 3860kb | C++20 | 2.3kb | 2024-10-01 20:28:58 | 2024-10-01 20:29:03 |
Judging History
answer
// Author: Olaf Surgut (surgutti)
// Created on 01-10-2024 14:06:24
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
#define endl '\n'
#define st first
#define nd second
#define pb push_bask
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, b, a) for (int i = (b); i >= (a); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define int long long
struct Point {
int x, y;
Point operator- (Point other) const {
return Point{x - other.x, y - other.y};
}
};
int det(Point A, Point B) {
return A.x * B.y - A.y * B.x;
}
Point dirs[4] = {Point{0, 1}, Point{1, 1}, Point{1, 0}, Point{1, -1}};
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<Point> pts(n);
for (auto& [x, y] : pts)
cin >> x >> y;
vector<map<int, int>> cnt(4);
FOR(i, 1, n - 1) {
Point P = pts[0], Q = pts[i];
FOR(dir_P, 0, 3) FOR(dir_Q, 0, 3) {
Point v = dirs[dir_P];
Point w = dirs[dir_Q];
if (det(v, w) == 0)
continue;
int p = det(Q - P, w);
int q = det(v, w);
if (abs(p) % abs(q) == 0) {
cnt[dir_P][p / q]++;
}
}
}
bool ok = false;
Point ans;
const int inf = 1'000'000'000;
auto test = [&](Point P) {
if (abs(P.x) > inf || abs(P.y) > inf)
return;
for (auto [x, y] : pts) {
if (x == P.x || y == P.y || abs(x - P.x) == abs(y - P.y))
continue;
return;
}
ok = true;
ans = P;
};
FOR(dir, 0, 3) {
int mx = 0;
int id = -1;
for (auto [a, b] : cnt[dir]) {
if (mx < b) {
mx = b;
id = a;
}
}
test(Point{pts[0].x + dirs[dir].x * id,
pts[0].y + dirs[dir].y * id});
}
if (ok)
cout << "YES\n" << ans.x << ' ' << ans.y << '\n';
else
cout << "NO\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3856kb
input:
3 2 1 1 2 2 4 0 1 1 0 3 1 4 0 5 0 1 1 0 1 2 2 2 4 2
output:
YES 0 2 NO YES 1 2
result:
ok OK (3 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
1 4 -100000000 -100000000 100000000 -100000000 -100000000 100000000 100000000 100000000
output:
YES -100000000 -100000000
result:
ok OK (1 test case)
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3860kb
input:
330 3 5 1 -3 -5 -2 2 2 1 4 4 0 4 2 -5 3 -3 -5 4 2 -2 2 -4 1 2 4 1 1 5 4 3 5 -2 3 5 2 -3 -3 5 -3 -4 2 -1 -2 -2 1 0 -1 -5 5 4 -3 -2 -4 2 2 0 -5 -4 -3 4 0 0 -3 -5 0 5 5 0 1 1 -1 5 0 2 3 4 1 4 4 5 5 0 3 -4 -5 -5 -3 5 -5 3 -1 2 -4 -4 -1 5 4 1 1 4 5 -1 0 5 2 1 -3 2 5 5 0 4 1 -3 -5 3 -3 0 0 5 0 1 -5 4 -5 5...
output:
YES 4 2 YES 4 1 NO YES -7 4 YES 0 6 NO NO NO NO YES 0 0 NO NO YES -4 5 YES 1 2 YES -4 3 NO YES -5 -4 YES -5 2 YES -5 -3 YES -2 0 NO YES 1 1 NO YES 5 1 YES 0 -1 YES 0 6 YES -6 -1 NO NO YES 10 -4 NO YES -3 3 YES 2 6 NO YES -6 2 NO NO YES 2 6 YES 2 0 YES 0 -3 YES -3 -4 NO YES -1 -3 YES 0 5 YES -3 -5 YE...
result:
wrong answer Jury found solution, but participant did not (test case 3)