QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#262773 | #7800. Every Queen | MikhailovBair# | WA | 1ms | 3484kb | C++17 | 5.6kb | 2023-11-23 23:46:40 | 2023-11-23 23:46:40 |
Judging History
answer
#include <bits/stdc++.h>
#define size(a) (ll)(a).size()
#define int long long
using namespace std;
mt19937_64 urng_64(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937 urng(chrono::high_resolution_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int INF = INT_MAX;
const ll INF_LL = LLONG_MAX;
const ld EPS = 1e-9;
const ll MOD = 1e9 + 7; //998244353;
struct point {
int x;
int y;
};
bool cmp1(const point p1, const point p2) {
return p1.x < p2.x;
}
bool cmp2(const point p1, const point p2) {
return p1.y < p2.y;
}
bool cmp3(const point p1, const point p2) {
return p1.x - p1.y < p2.x - p2.y;
}
bool cmp4(const point p1, const point p2) {
return p1.x + p1.y < p2.x + p2.y;
}
bool check(int x, int y, const vector<point> & v) {
for (point p : v) {
if (p.x != x and p.y != y and abs(p.x - x) != abs(p.y - y))
return false;
}
return true;
}
void solve() {
int n, curr1, curr2, curr_x, curr_y, t;
cin >> n;
vector <point> v(n);
for (int i = 0; i < n; ++i) {
cin >> v[i].x >> v[i].y;
}
// по X
sort(v.begin(), v.end(), cmp1);
curr1 = v[0].x;
curr2 = v[n - 1].x;
if (curr1 == curr2) {
cout << "YES" << "\n";
cout << v[0].x << " " << v[0].y << "\n";
return;
}
else {
curr_x = v[0].x;
curr_y = v[n - 1].y;
if (check(curr_x, curr_y, v)) {
cout << "YES" << "\n";
cout << curr_x << " " << curr_y << "\n";
return;
}
curr_x = v[0].x;
curr_y = v[0].x - (v[n - 1].x - v[n - 1].y);
if (check(curr_x, curr_y, v)) {
cout << "YES" << "\n";
cout << curr_x << " " << curr_y << "\n";
return;
}
curr_x = v[0].x;
curr_y = (v[n - 1].x + v[n - 1].y) - v[0].x;
if (check(curr_x, curr_y, v)) {
cout << "YES" << "\n";
cout << curr_x << " " << curr_y << "\n";
return;
}
}
// по Y
sort(v.begin(), v.end(), cmp2);
curr1 = v[0].y;
curr2 = v[n - 1].y;
if (curr1 == curr2) {
cout << "YES" << "\n";
cout << v[0].x << " " << v[0].y << "\n";
return;
}
else {
curr_x = v[n - 1].x;
curr_y = v[0].y;
if (check(curr_x, curr_y, v)) {
cout << "YES" << "\n";
cout << curr_x << " " << curr_y << "\n";
return;
}
curr_x = v[n - 1].x - v[n - 1].y + v[0].y;
curr_y = v[0].y;
if (check(curr_x, curr_y, v)) {
cout << "YES" << "\n";
cout << curr_x << " " << curr_y << "\n";
return;
}
curr_x = v[n - 1].x + v[n - 1].y - v[0].y;
curr_y = v[0].y;
if (check(curr_x, curr_y, v)) {
cout << "YES" << "\n";
cout << curr_x << " " << curr_y << "\n";
return;
}
}
// по X - Y
sort(v.begin(), v.end(), cmp3);
curr1 = v[0].x - v[0].y;
curr2 = v[n - 1].x - v[n - 1].y;
if (curr1 == curr2) {
cout << "YES" << "\n";
cout << v[0].x << " " << v[0].y << "\n";
return;
}
else {
t = curr1;
curr_x = v[n - 1].x;
curr_y = v[n - 1].x - t;
if (check(curr_x, curr_y, v)) {
cout << "YES" << "\n";
cout << curr_x << " " << curr_y << "\n";
return;
}
curr_x = t + v[n - 1].y;
curr_y = v[n - 1].y;
if (check(curr_x, curr_y, v)) {
cout << "YES" << "\n";
cout << curr_x << " " << curr_y << "\n";
return;
}
curr_x = (t + v[n - 1].x + v[n - 1].y) / 2;
curr_y = (-t + v[n - 1].x + v[n - 1].y) / 2;
if (check(curr_x, curr_y, v)) {
cout << "YES" << "\n";
cout << curr_x << " " << curr_y << "\n";
return;
}
}
// по X + Y
sort(v.begin(), v.end(), cmp4);
curr1 = v[0].x + v[0].y;
curr2 = v[n - 1].x + v[n - 1].y;
if (curr1 == curr2) {
cout << "YES" << "\n";
cout << v[0].x << " " << v[0].y << "\n";
return;
}
else {
t = curr1;
curr_x = v[n - 1].x;
curr_y = t - v[n - 1].x;
//cout << curr_x << " " << curr_y << "\n";
if (check(curr_x, curr_y, v)) {
cout << "YES" << "\n";
cout << curr_x << " " << curr_y << "\n";
return;
}
curr_x = t - v[n - 1].y;
curr_y = v[n - 1].y;
//cout << curr_x << " " << curr_y << "\n";
if (check(curr_x, curr_y, v)) {
cout << "YES" << "\n";
cout << curr_x << " " << curr_y << "\n";
return;
}
curr_x = (t + v[n - 1].x - v[n - 1].y) / 2;
curr_y = (t - (v[n - 1].x - v[n - 1].y)) / 2;
//cout << curr_x << " " << curr_y << "\n";
if (check(curr_x, curr_y, v)) {
cout << "YES" << "\n";
cout << curr_x << " " << curr_y << "\n";
return;
}
}
cout << "NO" << "\n";
return;
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin.tie(0);
ios::sync_with_stdio(0);
cout.precision(20);
int t;
cin >> t;
for (int i = 1; i <= t; ++i)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3484kb
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 1 2 NO YES 1 2
result:
ok OK (3 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3436kb
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: 3452kb
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 -3 1 YES 1 0 NO YES -4 4 YES 1 5 NO NO NO YES 0 -5 YES 1 -1 NO YES -5 -5 YES -4 5 YES 1 2 YES -3 2 NO YES -5 -4 YES -3 2 YES -5 -3 YES 1 -3 NO YES 2 0 NO NO YES 0 -1 YES 1 5 YES -5 -2 YES 4 6 NO YES 5 -4 NO YES 1 -4 YES 3 5 YES -1 3 YES -5 1 NO NO YES 2 5 YES 2 8 YES 1 -4 YES -2 -5 YES -6 -5 YES...
result:
wrong answer Jury found solution, but participant did not (test case 3)