QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#627063 | #7800. Every Queen | IllusionaryDominance# | WA | 37ms | 3896kb | C++20 | 2.9kb | 2024-10-10 14:37:39 | 2024-10-10 14:37:45 |
Judging History
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 << 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], 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: 3840kb
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: 3708kb
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: 3896kb
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 Yes ...
result:
ok OK (330 test cases)
Test #4:
score: -100
Wrong Answer
time: 37ms
memory: 3836kb
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 -4 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 Jury found solution, but participant did not (test case 229)