QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#627137#7800. Every QueenIllusionaryDominance#WA 34ms3852kbC++202.8kb2024-10-10 14:54:272024-10-10 14:54:28

Judging History

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

  • [2024-10-10 14:54:28]
  • 评测
  • 测评结果:WA
  • 用时:34ms
  • 内存:3852kb
  • [2024-10-10 14:54:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const double eps = 1e-6;

const double dA[] = {1, 0, 1, 1};
const double dB[] = {0, 1, 1, -1};

struct Point{
	double x, y;
}P[N];
int n;

struct Line{double A, B, C;};

bool check_on_line(Point p, Line l){return abs(l.A * p.x + l.B * p.y + l.C) <= eps;}
bool legal_point(Point p){return abs(p.x) <= 1e9 && abs(p.y) <= 1e9 && (p.x - round(p.x)) <= eps && (p.y - round(p.y)) <= eps;}
Line calc_line(Point p, int fx){return (Line){dA[fx], dB[fx], - dA[fx] * p.x - dB[fx] * p.y};}
Point cross_line(Line l1, Line l2){
	if(l1.A == 0) swap(l1, l2);
	if(l2.A){l2.A -= l1.A, l2.B -= l1.B, l2.C -= l1.C;}
	double y = -l2.C / l2.B;
	double x = (-l1.B * y - l1.C) / l1.A;
	return (Point){x, y};
}


map<double, int>ids;

bool check(Point p){
	for (int i = 1; i <= n; ++ i){
		int flag = 0;
		for (int fx = 0; fx < 4; ++ fx) flag |= check_on_line(p, (Line){dA[fx], dB[fx], - dA[fx] * P[i].x - dB[fx] * P[i].y});
		if(flag == 0) return 0;
	}
	return 1;
}

pair<int, Point> two_point_check(Point p1, Point p2){
	for (int fx1 = 0; fx1 < 4; ++ fx1)
		for (int fx2 = 0; fx2 < 4; ++ fx2){
			if(fx1 == fx2) continue;
			Point p = cross_line((Line){dA[fx1], dB[fx1], - dA[fx1] * p1.x - dB[fx1] * p1.y}, (Line){dA[fx2], dB[fx2], - dA[fx2] * p2.x - dB[fx2] * p2.y});
			if(legal_point(p) && check(p)) return make_pair(1, p);
		}
	return make_pair(-1, (Point){0, 0});
}

pair<int, Point> find(double A, double B){
	ids.clear();
	
	for (int i2 = 1; i2 <= n; ++ i2){
		if(ids[A * P[i2].x + B * P[i2].y]){
			int i1 = ids[A * P[i2].x + B * P[i2].y];
			Line l = (Line){A, B, - A * P[i2].x - B * P[i2].y};
			for (int i = 1; i <= n; ++ i)
				if (!check_on_line(P[i], l)){
					for (int fx = 0; fx < 4; ++ fx){
						Point p = cross_line(l, (Line){dA[fx], dB[fx], - dA[fx] * P[i].x - dB[fx] * P[i].y});
						if(legal_point(p) && check(p)) return make_pair(1, p);
					}
					break;
				}
			pair<int, Point> re = two_point_check(P[i1], P[i2]);
			return re;
		}
		ids[A * P[i2].x + B * P[i2].y] = i2;
	}
	return make_pair(0, (Point){0, 0});
}

void print(pair<int, Point> ans){
	cout << (ans.first == 1 ? "Yes\n" : "No\n");
	if(ans.first == 1) cout << int(ans.second.x) << " " << int(ans.second.y) << "\n";
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	int T; cin >> T;
	while(T --){
		cin >> n;
		
		for (int i = 1; i <= n; ++ i) cin >> P[i].x >> P[i].y;
		
		if(n == 1) {print(make_pair(1, P[1])); continue;}
		
		
		int flag = 0;
		
		for (int i = 0; i < 4; ++ i){
			pair<int, Point> ans = find(dA[i], dB[i]);
			if(ans.first != 0){print(ans); flag = 1; break;}
		}
		
		if(flag) continue;
		
		pair<int, Point> ans = two_point_check(P[1], P[2]);
		
		print(ans);
		
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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: 1ms
memory: 3708kb

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
5 -5
Yes
1 0
Yes
2 -3
Yes
-4 4
Yes
1 5
No
No
No
Yes
0 -5
Yes
1 -1
No
Yes
-5 -5
Yes
-1 -4
Yes
1 2
Yes
-3 2
No
Yes
-5 -4
Yes
-3 2
Yes
-5 -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
5 -4
No
Yes
4 3
Yes
3 5
Yes
-1 3
Yes
-5 1
No
No
Yes
3 -2
Yes
2 4
Yes
1 -4
Yes
...

result:

ok OK (330 test cases)

Test #4:

score: -100
Wrong Answer
time: 34ms
memory: 3784kb

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
5 4
Yes
-5 -4
No
Yes
-2 2
No
Yes
-5 -5
Yes
-3 0
No
Yes
-5 0
Yes
-3 -3
Yes
3 -2
Yes
5 -2
Yes
5 2
No
Yes
-5 4
No
Yes
4 -3
Yes
-2 1
Yes
-3 1
Yes
-2 -3
No
Yes
0 1
Yes
3 5
No
No
Yes
2 2
Yes
-4 -4
Yes
2 -3
Yes
4 -5
Yes
4 -2
Yes
-1 7
No
Yes
4 0
No
Yes
1 -3
Yes
3 -1
No
No
Yes
0 2
No
Yes
1 -5
Yes
-1 4...

result:

wrong answer Queen (4, 1) does not attack square (1, 3) (test case 317)