QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#262773#7800. Every QueenMikhailovBair#WA 1ms3484kbC++175.6kb2023-11-23 23:46:402023-11-23 23:46:40

Judging History

你现在查看的是最新测评结果

  • [2023-11-23 23:46:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3484kb
  • [2023-11-23 23:46:40]
  • 提交

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)