QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#260831 | #7800. Every Queen | Geospiza# | WA | 0ms | 3744kb | C++20 | 2.9kb | 2023-11-22 15:50:25 | 2023-11-22 15:50:26 |
Judging History
answer
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define Ma 1000005
#define G 3
#define N 512
#define pb push_back
#define L (1<<21)
#define eps 1e-2
#define PLL pair<ll,ll>
#define fi first
#define se second
#define all(x) x.begin(),x.end()
using namespace std;
ll inf=1e18;
ll sgn(double x)
{
if (x>eps) return 1;
if (x<-eps) return -1;
return 0;
}
struct Point{
double x,y;
Point operator -(Point b){
return {x-b.x,y-b.y};
}
Point operator +(Point b){
return {x+b.x,y+b.y};
}
double operator ^(Point b){
return x*b.y-y*b.x;
}
double operator *(Point b){
return x*b.x+y*b.y;
}
};
struct Line{
Point s,e;
ll relation(Point p){
ll c=sgn((p-s)^(e-s));
if (c<0) return 1;
else if (c>0) return 2;
return 3;
}
bool parallel(Line v){
return sgn((e-s)^(v.e-v.s))==0;
}
ll linecrossline(Line v){
if ((*this).parallel(v))
return v.relation(s)==3;
return 2;
}
Point crosspoint(Line v){
double a1=(v.e-v.s)^(s-v.s);
double a2=(v.e-v.s)^(e-v.s);
return Point({(s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1)});
}
};
ll n;
map <PLL,ll> mp;
vector <Line> v;
ll flag=0;
void check(Line x)
{
ll ans=0;
vector <PLL> add;
for (auto z:v)
{
ll op=x.linecrossline(z);
if (op==0)
continue;
else if (op==1)
ans++;
else
{
Point a=x.crosspoint(z);
if ((ll)(a.x+eps)==(ll)(a.x+0.5+eps))
add.pb({(ll)(a.x+eps),(ll)(a.y+eps)});
}
}
sort(all(add));
PLL pre={inf,inf};
ll cnt=0;
for (auto z:add)
{
if (z==pre)
cnt++;
else
{
cnt=1;
pre=z;
}
ll ck=cnt+ans;
if (mp.count(z))
ck-=3;
if (ck>=n)
{
flag=1;
printf("YES\n");
printf("%lld %lld\n",z.fi,z.se);
return;
}
}
}
void sol()
{
mp.clear(),v.clear();
flag=0;
cin>>n;
for (ll i=1;i<=n;i++)
{
ll x,y;
cin>>x>>y;
mp[{x,y}]++;
Point a={x,y};
v.pb({a,{a.x,a.y+1}});
v.pb({a,{a.x+1,a.y}});
v.pb({a,{a.x+1,a.y+1}});
v.pb({a,{a.x+1,a.y-1}});
}
for (ll i=0;i<4;i++)
{
check(v[i]);
if (flag)
return;
}
printf("NO\n");
return;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int tt=1;
cin>>tt;
while (tt--)
sol();
return 0;
}
/*
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3744kb
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 YES 0 0 YES 1 2
result:
wrong answer Queen (3, 1) does not attack square (0, 0) (test case 2)