QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#603870#7800. Every Queensurgutti#WA 0ms3860kbC++202.3kb2024-10-01 20:28:582024-10-01 20:29:03

Judging History

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

  • [2024-10-01 20:29:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3860kb
  • [2024-10-01 20:28:58]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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)