QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#627029#7800. Every QueenIllusionaryDominance#WA 1ms3868kbC++202.9kb2024-10-10 14:30:582024-10-10 14:31:03

Judging History

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

  • [2024-10-10 14:31:03]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3868kb
  • [2024-10-10 14:30:58]
  • 提交

answer

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

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

const int dA[] = {1, 0, 1, 1};
const int 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 - floor(p.x)) <= eps && (p.y - floor(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, int disable_fx){
	for (int fx1 = 0; fx1 < 4; ++ fx1)
		for (int fx2 = 0; fx2 < 4; ++ fx2){
			if(fx1 == disable_fx || fx2 == disable_fx || 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(int A, int B, int disable_fx){
	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], disable_fx);
			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 << fixed << setprecision(0) << ans.second.x << " " << 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], i);
			if(ans.first != 0){print(ans); flag = 1; break;}
		}
		
		if(flag) continue;
		
		pair<int, Point> ans = two_point_check(P[1], P[2], -1);
		
		print(ans);
		
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3868kb

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

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

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
-6 -3
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
Ye...

result:

wrong output format Expected integer, but "-0" found (test case 2)