QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#371160 | #7800. Every Queen | kevinyang# | WA | 1ms | 3824kb | C++17 | 4.1kb | 2024-03-30 01:04:50 | 2024-03-30 01:04:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator*(T d) const { return P(x*d, y*d); }
P operator/(T d) const { return P(x/d, y/d); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y - y*p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x*x + y*y; }
double dist() const { return sqrt((double)dist2()); }
// angle to x-axis in interval [-pi, pi]
double angle() const { return atan2(y, x); }
P unit() const { return *this/dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")"; }
};
typedef Point<int> P;
template<class P>
pair<int, P> lineInter(P s1, P e1, P s2, P e2) {
auto d = (e1 - s1).cross(e2 - s2);
if (d == 0) // if parallel
return {-(s1.cross(e1, s2) == 0), P(0, 0)};
auto p = s2.cross(e1, e2), q = s2.cross(e2, s1);
return {1, (s1 * p + e1 * q) / d};
}
bool good(P a, P b){
int dx = a.x - b.x;
int dy = a.y - b.y;
if(dx == 0 || dy == 0 || abs(dx) == abs(dy)){
return true;
}
return false;
}
bool diag(P a, P b){
int dx = a.x - b.x;
int dy = a.y - b.y;
if(dx == 0 || dy == 0)return false;
return true;
}
vector<P> merge(vector<P> a, vector<P> b){
set<P>s;
for(auto nxt: a){
s.insert(nxt);
}
vector<P>ans;
for(auto nxt: b){
if(s.find(nxt) == s.end())continue;
ans.push_back(nxt);
}
return ans;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector<P>arr(n);
for(int i = 0; i<n; i++){
int x,y;
cin >> x >> y;
arr[i] = P{x,y};
}
if(n==1){
cout << "YES\n";
cout << arr[0].x << ' ' << arr[0].y << '\n';
continue;
}
vector<int>dx = {-1,0,1,1};
vector<int>dy = {-1,-1,-1,0};
bool found = false;
for(int j = 0; j<2; j++){
for(int dir = 0; dir<4; dir++){
if(found)break;
P p = P{arr[j].x+dx[dir], arr[j].y+dy[dir]};
vector<vector<P>>ans(n);
bool bad = false;
bool onepoint = false;
for(int i = 0; i<n; i++){
if(i==j)continue;
if(diag(arr[j],p)){
int m = (arr[j].x + arr[j].y)%2;
m+=2; m%=2;
int m2 = (arr[i].x + arr[i].y)%2;
m2+=2; m2%=2;
if(m!=m2){
bad = true;
continue;
}
}
if((arr[j]-p).cross(arr[i]-arr[j]) == 0)continue;
for(int d = 0; d<4; d++){
P p2 = P{arr[i].x+dx[d], arr[i].y+dy[d]};
auto res = lineInter(arr[j],p,arr[i],p2);
if(res.first != 1)continue;
ans[i].push_back(res.second);
onepoint = true;
}
}
if(bad){
continue;
}
if(!onepoint){
cout << "YES\n";
cout << arr[j].x << ' ' << arr[j].y << '\n';
found = true;
break;
}
bool start = false;
vector<P>cur;
for(int a = 0; a<n; a++){
if(!start && ans[a].size()){
cur = ans[a];
start = true;
}
else if(ans[a].size()){
cur = merge(cur,ans[a]);
}
}
if(cur.size()){
cout << "YES\n";
cout << cur[0].x << ' ' << cur[0].y << '\n';
found = true;
break;
}
}
if(found)break;
}
if(found)continue;
cout << "NO\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3676kb
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 1 NO YES 1 2
result:
ok OK (3 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3824kb
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: 3660kb
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 -2 -6 YES 1 -3 YES 2 -3 YES -4 -2 YES 1 5 NO NO NO YES 0 -5 YES 1 -1 NO YES -7 -5 YES -1 -1 YES 1 2 YES -3 2 NO YES -5 -4 YES -3 -3 YES -5 -3 YES -2 0 NO YES 2 0 YES -1 -2 YES 5 1 YES 0 -1 YES 1 5 YES -5 -2 NO NO YES 5 5 NO YES 1 -7 YES 3 5 YES -1 -1 YES -5 1 NO NO YES 2 4 YES 2 4 YES 1 -4 YES -...
result:
wrong answer Jury found solution, but participant did not (test case 28)