这年 WF 较为简单的一道了，直接模拟即可。首先可以预处理出它顺时针螺旋轨迹的移动步数，方便过会算距离直接查表。我偷懒直接用 map 记录的距离表，这样不用处理复数下标的问题。注意到 \(X\) 的数量不会超过 \(100\) 个，所以我们可以反过来从标记点上入手。找出所有的标记点，记录下每个位置到每个标记点的距离并将这些距离从小到大排序，然后将每个位置按照“到每个 \(X\) 的距离构成的序列”的字典序排序，这样无法区分所在位置的一定是在排序后序列中相邻的两项，因为它们有最长的公共前缀，可以直接暴力遍历算。最后统计答案即可。如果视查询 map 复杂度为 \(\mathcal O(1)\) 的话，记 \(T\) 为 \(X\) 标记的数量，复杂度 \(\mathcal O(d_x d_y T \log T)\)。
#include<bits/stdc++.h>
#define int long long
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define eb emplace_back
#define pb pop_back
#define ins insert
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define power(x) ((x)*(x))
#define gcd(x,y) (__gcd((x),(y)))
#define lcm(x,y) ((x)*(y)/gcd((x),(y)))
#define lg(x,y) (__lg((x),(y)))
using namespace std;
namespace FastIO
{
template<typename T=int> inline T read()
{
T s=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
return s*w;
}
template<typename T> inline void read(T &s)
{
s=0; int w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
s=s*w;
}
template<typename T,typename... Args> inline void read(T &x,Args &...args)
{
read(x),read(args...);
}
template<typename T> inline void write(T x,char ch)
{
if(x<0) x=-x,putchar('-');
static char stk[25]; int top=0;
do {stk[top++]=x%10+'0',x/=10;} while(x);
while(top) putchar(stk[--top]);
putchar(ch);
return;
}
}
using namespace FastIO;
namespace MTool
{
#define TA template<typename T,typename... Args>
#define TT template<typename T>
static const int Mod=1e9+9;
TT inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
TT inline void cmax(T &a,T b) {a=a>b?a:b;}
TT inline void cmin(T &a,T b) {a=a<b?a:b;}
TT inline void Madd(T &a,T b) {a=a+b>Mod?a+b-Mod:a+b;}
TT inline void Mdel(T &a,T b) {a=a-b<0?a-b+Mod:a-b;}
TT inline void Mmul(T &a,T b) {a=a*b%Mod;}
TT inline void Mmod(T &a) {a=(a%Mod+Mod)%Mod;}
TT inline T Cadd(T a,T b) {return a+b>=Mod?a+b-Mod:a+b;}
TT inline T Cdel(T a,T b) {return a-b<0?a-b+Mod:a-b;}
TT inline T Cmul(T a,T b) {return a*b%Mod;}
TT inline T Cmod(T a) {return (a%Mod+Mod)%Mod;}
TA inline void Madd(T &a,T b,Args... args) {Madd(a,Cadd(b,args...));}
TA inline void Mdel(T &a,T b,Args... args) {Mdel(a,Cadd(b,args...));}
TA inline void Mmul(T &a,T b,Args... args) {Mmul(a,Cmul(b,args...));}
TA inline T Cadd(T a,T b,Args... args) {return Cadd(Cadd(a,b),args...);}
TA inline T Cdel(T a,T b,Args... args) {return Cdel(Cdel(a,b),args...);}
TA inline T Cmul(T a,T b,Args... args) {return Cmul(Cmul(a,b),args...);}
TT inline T qpow(T a,T b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
TT inline T qmul(T a,T b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
TT inline T spow(T a,T b) {int res=1; while(b) {if(b&1) res=qmul(res,a); a=qmul(a,a); b>>=1;} return res;}
TT inline void exgcd(T A,T B,T &X,T &Y) {if(!B) return X=1,Y=0,void(); exgcd(B,A%B,Y,X),Y-=X*(A/B);}
TT inline T Ginv(T x) {T A=0,B=0; exgcd(x,Mod,A,B); return Cmod(A);}
#undef TT
#undef TA
}
using namespace MTool;
inline void file()
{
freopen(".in","r",stdin);
freopen(".out","w",stdout);
return;
}
bool Mbe;
namespace LgxTpre
{
static const int MAX=100010;
static const int inf=2147483647;
static const int INF=4557430888798830399;
static const int mod=1e9+7;
static const int bas=131;
int n,m;
char c;
vector<pii> X,ans; int Xcnt;
map<pii,int> dis;
int dissum,dismix;
struct lmy
{
int x,y,dis;
vector<int> tox;
lmy(int X=0,int Y=0,int Dis=0):x(X),y(Y),dis(Dis) {}
};
vector<lmy> all;
inline void lmy_forever()
{
read(n,m);
for(int x=0,y=0,step=0,stepn=1,cur=0,dx=0,dy=1;cur<=40400;++cur)
{
dis[mp(x,y)]=cur,x+=dx,y+=dy;
if(++step==stepn) Swp(dx,dy),dy=-dy,step=0,stepn+=(dy!=0);
}
for(int j=m;j>=1;--j) for(int i=1;i<=n;++i)
{
do c=getchar(); while(c!='X'&&c!='.');
if(c=='X') X.eb(mp(i,j));
}
Xcnt=X.size();
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
{
lmy now; now.x=i,now.y=j;
for(auto it:X) now.tox.eb(dis[mp(it.fi-i,it.se-j)]);
sort(now.tox.begin(),now.tox.end()),all.eb(now);
}
sort(all.begin(),all.end(),[&](lmy a,lmy b){for(int i=0;i<Xcnt;++i) if(a.tox[i]!=b.tox[i]) return a.tox[i]<b.tox[i];});
for(int i=1;i<((int)all.size());++i) for(int j=0;j<Xcnt;++j) if(all[i].tox[j]!=all[i-1].tox[j])
{
cmax(all[i].dis,min(all[i].tox[j],all[i-1].tox[j])),
cmax(all[i-1].dis,min(all[i].tox[j],all[i-1].tox[j]));
break;
}
for(auto it:all) cmax(dismix,it.dis),dissum+=it.dis;
cout<<fixed<<setprecision(9)<<1.0*dissum/((int)all.size())<<'\n'<<dismix<<'\n';
for(auto it:all) if(it.dis==dismix) ans.eb(mp(it.y,it.x));
sort(ans.begin(),ans.end());
for(auto it:ans) putchar('('),write(it.se,','),write(it.fi,')'),putchar(' ');
return puts(""),void();
}
}
bool Med;
signed main()
{
// file();
fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
int Tbe=clock();
LgxTpre::lmy_forever();
int Ted=clock();
cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
return (0-0);
}