QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#614454#7800. Every QueenKyy008WA 144ms3808kbC++147.3kb2024-10-05 16:22:412024-10-05 16:22:44

Judging History

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

  • [2024-10-05 16:22:44]
  • 评测
  • 测评结果：WA
  • 用时：144ms
  • 内存：3808kb
查看
  • [2024-10-05 16:22:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define rep(i, f, l) for(int i=(f); i <= (l); ++i)
#define per(i, f, l) for(int i=(f); i >= (l); --i)
const int N = 1e5 + 5;

struct Queen {
	int x;
	int y;
};

struct MainLine {
	string type;
	int c;
};

bool align(Queen q1, Queen q2,  Queen q3) {
	return (q2.x - q1.x) * (q3.y - q1.y) == (q3.x - q1.x) * (q2.y - q1.y);
}


bool judge(const Queen &q1, const Queen &q2, const Queen &q3, MainLine &line) {
	if (q1.x == q2.x && q2.x == q3.x) {
		line.type = "ver";
		line.c = q1.x;
		return true;
	}
	if (q1.y == q2.y && q2.y == q3.y) {
		line.type = "hori";
		line.c = q1.y;
		return true;
	}

	if ((q2.x - q1.x) != 0) {

		if ((q2.y - q1.y) == (q2.x - q1.x) && (q3.y - q1.y) == (q3.x - q1.x)) {
			line.type = "dia1";
			line.c = q1.y - q1.x;
			return true;
		}

		if ((q2.y - q1.y) == -(q2.x - q1.x) && (q3.y - q1.y) == -(q3.x - q1.x)) {
			line.type = "dia2";
			line.c = q1.y + q1.x;
			return true;
		}
	}
	return false;
}

// 检查一个皇后是否在主线上
bool online(const Queen &q, const MainLine &line) {
	if (line.type == "ver") {
		return q.x == line.c;
	}
	if (line.type == "hori") {
		return q.y == line.c;
	}
	if (line.type == "dia1") {
		return q.y == q.x + line.c;
	}
	if (line.type == "dia2") {
		return q.y == -q.x + line.c;
	}
	return false;
}

// 获取一个皇后攻击线与主线的交点
vector<pair<int, int>> getnode(const Queen &q, const MainLine &line) {
	vector<pair<int, int>> tmp;

	if (line.type == "ver") {

		tmp.emplace_back(line.c, q.y);

		tmp.emplace_back(line.c, line.c + (q.x - q.y));

		tmp.emplace_back(line.c, -line.c + (q.x + q.y));
	} else if (line.type == "hori") {
		tmp.emplace_back(q.x, line.c);
		tmp.emplace_back(line.c - (q.x - q.y), line.c);
		tmp.emplace_back((q.x + q.y) - line.c, line.c);
	} else if (line.type == "dia1") {

		tmp.emplace_back(q.x, q.x + line.c);

		tmp.emplace_back(q.y - line.c, q.y);

		if (((q.x + q.y) - line.c) % 2 == 0) {
			int x = ((q.x + q.y) - line.c) / 2;
			int y = x + line.c;
			tmp.emplace_back(x, y);
		}
	} else if (line.type == "dia2") {

		tmp.emplace_back(q.x, -q.x + line.c);

		tmp.emplace_back(line.c - q.y, q.y);

		if ((line.c - (q.x - q.y)) % 2 == 0) {
			int x = (line.c - (q.x - q.y)) / 2;
			int y = -x + line.c;
			tmp.emplace_back(x, y);
		}
	}

	return tmp;
}

struct Line {
	string type; // "x", "y", "c", "d"
	int val;
};
struct Line1{
    int x;
    int y;
    int c;
    int d;
};
Line1 get_line(Queen q){
    Line1 l;
    l.x = q.x;
    l.y = q.y;
    l.c = q.x - q.y;
    l.d = q.x + q.y;
    return l;
}
// 获取一个皇后的攻击线
vector<Line> getlines(const Queen &q) {
	vector<Line> lines;
	lines.push_back(Line{"x", q.x});
	lines.push_back(Line{"y", q.y});
	lines.push_back(Line{"c", q.x - q.y});
	lines.push_back(Line{"d", q.x + q.y});
	return lines;
}

void work() {
	int n;
	cin >> n;
	vector<Queen> queens(n);
	for (int i = 0; i < n; i++) {
		cin >> queens[i].x >> queens[i].y;
	}
	if (n == 1) {
		cout << "YES\n" << queens[0].x << ' ' << queens[0].y << '\n';
		return;
	}

	// 检查前三个皇后是否共线
	bool f1 = false;
	MainLine main_line;
	if (n >= 3 && align(queens[0], queens[1], queens[2])) {
		if (judge(queens[0], queens[1], queens[2], main_line)) {
			f1 = true;
		}
	}
	if (f1) {
		vector<pair<int, int>> nodes;
		bool all_on_line = true;
		for (int i = 0; i < n; i++) {
			if (online(queens[i], main_line)) {
				continue;
			}
			all_on_line = false;
			vector<pair<int, int>> inters = getnode(queens[i], main_line);
			for (auto &p : inters) {
				nodes.emplace_back(p);
			}
		}
		if (all_on_line) {
			cout << "YES\n" << queens[0].x << ' ' << queens[0].y << '\n';
			return;
		}
		sort(nodes.begin(), nodes.end());
		nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
		// 检查每个候选点是否被所有皇后攻击
		bool found = false;
		pair<int, int> answer;
		for (auto &p : nodes) {
			int x = p.first;
			int y = p.second;
			bool valid = true;
			for (int i = 0; i < n; i++) {
				if (x == queens[i].x || y == queens[i].y || abs(x - queens[i].x) == abs(y - queens[i].y)) {
					continue;
				} else {
					valid = false;
					break;
				}
			}
			if (valid) {
				answer = p;
				found = true;
				break;
			}
		}
		if (found) {
			cout << "YES\n" << answer.first << ' ' << answer.second << '\n';
		} else {
			cout << "NO\n";
		}
	}
	/*
1
5
-1 0
1 0
2 0
9 0
10 10
		*/
	else {
		//原算法
		int k = min((int)3, n);
		vector<pair<int, int> > node;
		vector<Queen> sel(queens.begin(), queens.begin() + k);
		for (int i = 0; i < k; i++) {
			for (int j = 0; j < k; j++) {
				Line1 ll1 = get_line(sel[i]);
				Line1 ll2 = get_line(sel[j]);
				vector<pair<string, int>> atk1 = { {"x", ll1.x}, {"y", ll1.y}, {"c", ll1.c}, {"d", ll1.d} };
				vector<pair<string, int>> atk2 = { {"x", ll2.x}, {"y", ll2.y}, {"c", ll2.c}, {"d", ll2.d} };
				for (auto &l1 : atk1) {
					for (auto &l2 : atk2) {
						string tmp1 = l1.first;
						int tmq1 = l1.second;
						string tmp2 = l2.first;
						int tmq2 = l2.second;
						int x, y;
						if (tmp1 == tmp2) {
							continue;
						}
						if (tmp1 == "x") {
							x = tmq1;
							if (tmp2 == "y") {
								y = tmq2;
							} else if (tmp2 == "c") {
								y = x - tmq2;
							} else if (tmp2 == "d") {
								y = tmq2 - x;
							} else {
								continue;
							}
						} else if (tmp1 == "y") {
							y = tmq1;
							if (tmp2 == "x") {
								x = tmq2;
							} else if (tmp2 == "c") {
								x = tmq2 + y;
							} else if (tmp2 == "d") {
								x = tmq2 - y;
							} else {
								continue;
							}
						} else if (tmp1 == "c") {
							if (tmp2 == "x") {
								x = tmq2;
								y = x - tmq1;
							} else if (tmp2 == "y") {
								y = tmq2;
								x = tmq1 + y;
							} else if (tmp2 == "d") {
								x = (tmq1 + tmq2) / 2;
								y = (tmq2 - tmq1) / 2;
							} else {
								continue;
							}
						} else if (tmp1 == "d") {
							if (tmp2 == "x") {
								x = tmq2;
								y = tmq1 - x;
							} else if (tmp2 == "y") {
								y = tmq2;
								x = tmq1 - y;
							} else if (tmp2 == "c") {
								x = (tmq1 + tmq2) / 2;
								y = (tmq1 - tmq2) / 2;
							} else {
								continue;
							}
						} else {
							continue;
						}
						node.emplace_back(x, y);
					}
				}
			}
		}
		sort(node.begin(), node.end());
		node.erase(unique(node.begin(), node.end()), node.end());
		bool f = 0;
		pair<int, int> ans;
		for (auto i = node.begin(); i != node.end(); i++) {
			int x = i->first;
			int y = i->second;
			bool is = 1;
			rep(i, 0, n - 1) {
				int xi = queens[i].x;
				int yi = queens[i].y;
				if (x == xi || y == yi || abs(x - xi) == abs(y - yi)) {
					continue;
				} else {
					is = 0;
					break;
				}
			}
			if (is) {
				ans = make_pair(x, y);
				f = 1;
				break;
			}
		}
		if (f) {
			cout << "YES" << endl;
			cout << ans.first << ' ' << ans.second << endl;
		} else {
			cout << "NO" << endl;
		}

	}

}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		work();
	}
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

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: 3548kb

input:

1
4
-100000000 -100000000
100000000 -100000000
-100000000 100000000
100000000 100000000

output:

YES
-100000000 -100000000

result:

ok OK (1 test case)

Test #3:

score: 0
Accepted
time: 0ms
memory: 3628kb

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
-3 0
YES
2 -3
YES
-7 4
YES
1 5
NO
NO
NO
YES
0 -5
YES
1 -1
NO
YES
-7 -5
YES
-4 2
YES
1 2
YES
-3 2
NO
YES
-5 -4
YES
-5 2
YES
-6 -4
YES
-2 0
NO
YES
2 0
YES
-1 -2
YES
5 1
YES
0 -1
YES
1 5
YES
-5 -2
YES
4 6
NO
YES
0 -4
NO
YES
-6 -4
YES
3 5
YES
-1 -1
YES
-5 1
NO
NO
YES
-5 5
YES
2 0
YES
1 -4
Y...

result:

ok OK (330 test cases)

Test #4:

score: -100
Wrong Answer
time: 144ms
memory: 3808kb

input:

33773
4
-2 -5
4 -1
-5 4
2 -1
3
5 1
1 0
-2 4
1
-5 -4
4
-3 1
5 -1
1 -2
-3 5
2
-2 -2
0 2
4
-2 -1
4 -5
1 1
1 -4
3
-5 -5
-5 0
-3 -5
1
-3 0
4
-5 -4
2 2
-5 -3
5 -3
1
-5 0
2
-3 -3
-4 -3
1
3 -2
3
-2 -2
5 -4
5 -3
2
5 -1
-5 2
4
0 -1
5 1
0 0
-4 -1
1
-5 4
4
-5 3
3 0
-1 -3
0 3
2
4 0
0 -3
2
-2 4
0 1
2
-3 3
4 1
3
-...

output:

NO
YES
1 1
YES
-5 -4
NO
YES
-6 2
NO
YES
-10 -5
YES
-3 0
NO
YES
-5 0
YES
-4 -4
YES
3 -2
YES
5 -9
YES
-8 -1
NO
YES
-5 4
NO
YES
-3 0
YES
-5 1
YES
-5 1
YES
-6 -3
NO
YES
0 1
YES
3 5
NO
NO
YES
0 0
YES
-4 -4
YES
2 -3
YES
4 -5
YES
-5 3
YES
-1 7
NO
YES
-3 3
NO
YES
1 -8
YES
-9 5
NO
NO
YES
-1 2
NO
YES
-9 1
YES...

result:

wrong answer Jury found solution, but participant did not (test case 7915)
English 繁體中文 简体中文

Server Time: 2024-12-03 06:33:08 | OpenSource Project