小H和棋盘-题解

很明显，当k>=n，对称点有无数个。
先对n个棋子进行排序，两个棋子的比较策略为：先对棋子横坐标进行比较，横坐标相同对纵坐标进行比较。
我们最多可以放k个棋子，所以，我们最多可以不管最左边棋子的k个棋子或者是最右边的k个棋子。
每次根据最左边和最右边的棋子选出一个对称点，然后判断该对称点之前是否使用过，
再判断所有棋子是否能在该对称点下满足题目条件，
判断整个棋子是否满足条件：先有两个左右指针L=1， R=n，然后判断L点和R点是否对称，可以先算出L的对称点，如果对称点比R小，则R不会再有对称点，比R大，则L不会再有对称点，该结论可以自己尝试发现。最多只能存在k个点找不到对称点。
最后得出ans。

代码如下：
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;</algorithm></map></iostream>

pair<int, int> s[100005];
map<pair<int, int>, bool> set;

bool check(int n, int k, pair<int, int> p)
{
int L = 1, R = n;
while (L <= R)
{
pair<int, int> m = make_pair(p.first - s[L].first, p.second - s[L].second);
if (m == s[R]) L++, R--;
else
{
if (!k) return 0;
k--;
if (m < s[R]) R--;
else L++;
}
}
return 1;
}

int main()
{
int n, k, ans = 0; scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%d%d", &s[i].first, &s[i].second);
if (k >= n)
{
printf("-1");
return 0;
}
sort(s + 1, s + 1 + n);
for (int i = 1; i <= k + 1; i++)
{
for (int j = n; j >= n - k - 1; j--)
{
if (j < i) break;
pair<int, int> p = make_pair(s[i].first + s[j].first, s[i].second + s[j].second);
if (set[p]) continue;
set[p] = 1;
if (check(n, k, p)) ans++;
}
}
printf("%d", ans);
return 0;
}