QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#260824 | #7800. Every Queen | Geospiza# | WA | 1ms | 3756kb | C++20 | 2.8kb | 2023-11-22 15:45:35 | 2023-11-22 15:45:36 |
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==(ll)(a.x+0.5+eps))
add.pb({(ll)a.x,(ll)a.y});
}
}
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: 100
Accepted
time: 1ms
memory: 3616kb
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: 3756kb
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: 3580kb
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 -3 YES 2 -3 YES 2 1 YES 1 5 NO NO NO YES 0 -5 YES 1 -1 NO NO YES 2 2 YES 1 2 NO NO NO YES 0 0 NO YES 0 -1 NO YES 2 0 YES 0 -1 YES 5 1 YES 0 -1 YES 1 5 NO YES 4 6 NO YES 5 -13 NO YES 4 0 YES 3 5 NO NO NO NO YES 3 -3 YES 2 4 YES 1 -4 NO NO YES 1 -5 YES 1 4 NO YES 2 2 NO NO NO YES 0 1 NO...
result:
wrong answer Jury found solution, but participant did not (test case 12)