题解：P16215 [ECUSTPC 2025] 化方为圆

· · 题解

题意简述

通过至多 35 次格点包含查询，区分以原点为中心的格点圆与格点正方形。若两种图形覆盖的格点集合相同，输出 NotConfirm。

解题思路

先询问 (10,0)。若它在图形内，则在 [10,2\times10^5] 内二分；否则在 [1,10] 内二分。设横轴上最远的内部格点为 (m,0)。若图形是半径为 r 的圆，则 m\le r<m+1。

取一个整数方向 (x,y)，记 q=x^2+y^2。定义两个整数：

\begin{aligned} l & =\left\lfloor\frac{m}{\sqrt q}\right\rfloor \\ u & =\left\lceil\frac{m+1}{\sqrt q}\right\rceil \end{aligned}

点 l(x,y) 到原点的距离不超过 m，所以它必然在候选圆内。点 u(x,y) 到原点的距离不小于 m+1，所以它必然在候选圆外。若任意一次回答与此矛盾，隐藏图形只能是正方形。代码用整数二分计算 l 和 u，不引入浮点误差。

使用的方向集合为：

D=\set{(1,1),(2,1),(1,2),(3,1),(1,3),(3,2),(2,3),(1,4),(4,1),(1,5),(5,1),(2,5),(5,2),(3,5),(5,3),(3,8),(8,3)}

根据题目的最新更正，正方形顶点坐标绝对值不超过 10^5。若 m>10^5，可直接确定图形是圆。当 10\le m\le10^5 时，仅检查前 6 个方向的两个点。当 m<10 时，前 6 个方向检查两个点，其余方向只检查圆外点。

下面说明这些方向足以排除所有可区分的正方形。利用旋转，可把正方形的一个顶点写成 (a,b)，其中 a\ge|b|\ge0。记 Q=a^2+b^2。格点 (X,Y) 在正方形内当且仅当：

|aX+bY|+|-bX+aY|\le Q

正方形在横轴上的连续截距为 h=\frac{Q}{a+|b|}，因此 m\le h<m+1。沿方向 (x,y) 的径向长度为：

\rho_{x,y}=\frac{\sqrt{x^2+y^2}Q}{|ax+by|+|ay-bx|}

令 t=\frac{|b|}{a}，以 \varepsilon\in\set{-1,1} 记录 b 的符号。可消去正方形的尺度：

\frac{\rho_{x,y}}{h}=\frac{\sqrt{x^2+y^2}(1+t)}{|x+\varepsilon ty|+|y-\varepsilon tx|}

对前 6 个方向，绝对值只会在 t=\frac{1}{3},\frac{1}{2},\frac{2}{3} 处改变符号。每段中的分子、分母都是一次式。把圆内点和圆外点的条件代入后，公共的 1+t 可约去，只剩有限组一次不等式。

在 10\le m\le10^5 内逐段求交，只有 m=12 和 m=15 的连续区间没有直接排空。又因为：

\frac{a+|b|}{2}\le\frac{a^2+b^2}{a+|b|}<m+1

这些情况都有 a+|b|<2(m+1)。枚举对应的整数对后，没有正方形能通过前 6 个方向。该检查只含整数与有理数运算。

当 m<10 时，同一不等式给出 a+|b|<20。枚举这些整数对。前 6 个方向检查内外点，其余方向检查圆外点。所有可区分的正方形都会被排除。

最后处理无法区分的情况。覆盖格点集合相同的正方形，其顶点绝对值排序后只有 (0,1)、(0,2)、(1,1)、(2,2)；对应圆的 r^2 分别属于 \set{1,2,4,8}。它们都满足 m\le2。

若探针全部符合圆且 m>2，答案为 Bumper。否则再询问 (1,2)、(2,1)、(2,2)。恰有两个点在图形内时，只可能是 r^2=5 的圆，答案仍为 Bumper；其他情况输出 NotConfirm。

当 m\ge10 时，轴向二分至多询问 19 次，方向探针询问 12 次。当 m<10 时，总询问次数不超过 30 次。因此总询问次数不超过 31 次。

参考代码

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

const int d[][2]={{1,1},{2,1},{1,2},{3,1},{1,3},{3,2},{2,3},{1,4},{4,1},{1,5},{5,1},{2,5},{5,2},{3,5},{5,3},{3,8},{8,3}};
bool ask(int x,int y)
{
    cout<<'?'<<' '<<x<<' '<<y<<'\n';
    cout.flush();
    string s;
    cin>>s;
    if(s=="-1")exit(0);
    return s=="IN";
}
void answer(int op)
{
    cout<<'!'<<' ';
    if(op==0)cout<<"Bumper";
    else if(op==1)cout<<"Kevin";
    else if(op==2)cout<<"NotConfirm";
    cout<<'\n';
    cout.flush();
    string s;
    cin>>s;
    if(s=="-2")exit(0);
}
int get(int x,int q)
{
    int l=0,r=x+1;
    while(l<r)
    {
        int m=(l+r)/2;
        if(1LL*m*m*q>1LL*x*x)r=m;
        else l=m+1;
    }
    return l-1;
}
void solve()
{
    bool in=ask(10,0);
    int l=in?10:1,r=in?200000:10;
    while(l+1<r)
    {
        int m=(l+r)/2;
        if(ask(m,0))l=m;
        else r=m;
    }
    int m=l;
    if(m>100000)
    {
        answer(0);
        return;
    }
    int n=m>=10?6:17;
    for(int i=0;i<n;i++)
    {
        int x=d[i][0],y=d[i][1],q=x*x+y*y;
        int a=get(m,q),b=get(m+1,q);
        if(1LL*b*b*q<1LL*(m+1)*(m+1))b++;
        if(i<6&&!ask(a*x,a*y))
        {
            answer(1);
            return;
        }
        if(ask(b*x,b*y))
        {
            answer(1);
            return;
        }
    }
    if(m>2)answer(0);
    else
    {
        int cnt=ask(1,2)+ask(2,1)+ask(2,2);
        if(cnt==2)answer(0);
        else answer(2);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}