LINK：小B的棋盘
考试的时候没有认真的思考 导致没做出来.
容易发现 当k>=n的时候存在无限解 其余都存在有限解
对于30分 容易想到暴力枚举 对称中心 然后 n^2判断.
对于前者 容易发现 对称中心为某个点或某两个点的中点 对于后者 可以发现排序过后双指针可以做。
双指针做的时候还是存在一些小细节的(爆零警告 两种属性 不可以随便判断就跳指针 得根据自己排序的顺序来判断是否跳指针.
拿到30之后还是考虑 对称中心的问题.
对于 一些点对的中点或者一些点当对称中心 显然是不合法的 如 以某个点为对称中心的时候的四个象限画出来 然后 很容易发现端倪。
且 最后最多只有k个点可以不匹配 且匹配的时候的点对也有相对顺序的关系.
如 左下方的点一定是和右上方的点尽可能匹配的 类似等等...
特殊的 考虑 最靠下且尽可能靠左的k+1个点 一定和 相对的 最靠上且尽可能靠右的k+1个点之间存在匹配关系。
如果没有一对存在 那么显然不存在合法解 存在的话我们直接进行判定 这样就把刚才n^2的点集变成了 k^2的点集。
带上双指针就是nk^2的了.
由此推测 这道题的60分做法是希望我们写一个hash来判断重复而不是sort 这样做的话 点集被缩小为k^2.
值得一提的是 这样还是存在一个比较常见的check 虽然两点的中点坐标公式需要/2 但是可以都乘以2 来更好的避免小数误差.
const int MAXN=100010,G=3;
int n,k,cnt,ans;
struct wy{int x,y;}t[MAXN],w[MAXN];
inline int cmp(wy a,wy b){return a.y==b.y?a.x<b.x:a.y<b.y;}
inline int pd(wy a,wy b){return a.x==b.x&&a.y==b.y;}
inline int calc(int x,int y)
{
int l=1,r=n,cnt=0;
while(l<=r)
{
if(l==r)
{
if(t[l].x*2!=x||t[r].y*2!=y)++cnt;
break;
}
if(t[l].x+t[r].x==x&&t[r].y+t[l].y==y)++l,--r;
else
{
++cnt;
if(t[r].y>y-t[l].y)--r;
else
{
if(t[r].y==y-t[l].y)
{
if(t[r].x>x-t[l].x)--r;
else ++l;
}
else ++l;
}
}
}
return cnt<=k;
}
int main()
{
freopen("1.in","r",stdin);
//freopen("a.out","w",stdout);
get(n);get(k);
if(k>=n){puts("-1");return 0;}
rep(1,n,i)
{
int get(x),get(y);
t[i]=(wy){x,y};
}
sort(t+1,t+1+n,cmp);
rep(1,k+1,i)rep(n-k,n,j)w[++cnt]=(wy){t[i].x+t[j].x,t[i].y+t[j].y};
sort(w+1,w+1+cnt,cmp);
rep(1,cnt,i)
{
if(i!=1&&pd(w[i],w[i-1]))continue;
ans+=calc(w[i].x,w[i].y);
}
put(ans);
return 0;
}