QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #614245 | #7800. Every Queen | Kyy008 | WA | 2ms | 3816kb | C++14 | 10.0kb | 2024-10-05 16:00:09 | 2024-10-05 16:00:11 |
Judging History
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;
};
// 获取一个皇后的攻击线
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";
}
}
else{
//原算法
int k = min((int)3, n);
vector<pair<int, int> > node;
vector<vector<Line>> attack_lines(k);
for(int i = 0; i < k; i++) {
attack_lines[i] = getlines(queens[i]);
}
for(int i = 0; i < k; i++){
for(int j = i+1; j < k; j++){
for(int m = 0; m < attack_lines[i].size(); m++){
for(int n_idx = 0; n_idx < attack_lines[j].size(); n_idx++){
Line l1 = attack_lines[i][m];
Line l2 = attack_lines[j][n_idx];
if(l1.type == l2.type){
continue;
}
int x, y;
if(l1.type == "x"){
x = l1.val;
if(l2.type == "y"){
y = l2.val;
}
else if(l2.type == "c"){
y = x - l2.val;
}
else if(l2.type == "d"){
y = l2.val - x;
}
else{
continue;
}
}
else if(l1.type == "y"){
y = l1.val;
if(l2.type == "x"){
x = l2.val;
}
else if(l2.type == "c"){
x = l2.val + y;
}
else if(l2.type == "d"){
x = l2.val - y;
}
else{
continue;
}
}
else if(l1.type == "c"){
if(l2.type == "x"){
x = l2.val;
y = x - l1.val;
}
else if(l2.type == "y"){
y = l2.val;
x = l1.val + y;
}
else if(l2.type == "d"){
x = (l2.val - l1.val) / 2;
y = x + l1.val;
}
else{
continue;
}
}
else if(l1.type == "d"){
if(l2.type == "x"){
x = l2.val;
y = l1.val - x;
}
else if(l2.type == "y"){
y = l2.val;
x = l1.val - y;
}
else if(l2.type == "c"){
x = (l1.val - l2.val) / 2;
y = l1.val - x;
}
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 = false;
pair<int ,int> ans;
for(auto &p : node){
int x = p.first;
int y = p.second;
bool is = true;
for(int i = 0; i < n; i++){
int xi = queens[i].x;
int yi = queens[i].y;
if(x == xi || y == yi || abs(x - xi) == abs(y - yi)){
continue;
}
else{
is = false;
break;
}
}
if(is){
ans = p;
f = true;
break;
}
}
if(f){
cout << "YES\n" << ans.first << ' ' << ans.second << '\n';
}
else{
cout << "NO\n";
}
}
}
signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
int t;
cin >> t;
while (t--) {
work();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
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: 3592kb
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: 2ms
memory: 3592kb
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:
wrong answer Jury found solution, but participant did not (test case 303)