Codeforces 140F（坐标系点对称）

要点

结论：如果坐标系一堆点两两对称于某一重心，则排序后第1个和第n个为一对，以此类推。
枚举所有可能的重心点并check。因为隐藏的点不超过k个，所以点1～k+1都可能跟第n个匹配。对右侧同样适用，因此枚举的点是\(k^2\)的。内部只要两边开始扫描，如果匹配不是当前重心则说明他俩不是一对，则加一个虚点（cnt++），最后加的虚点数不超过k即true。

#include <cstdio>

#include <algorithm>

#include <set>

#define fir first

#define sec second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 2e5 + 5;

int n, k;

pii p[maxn];

set<pii> s;

pii operator + (pii A, pii B) {

	return {A.fir + B.fir, A.sec + B.sec};

}

bool operator == (pii A, pii B) {

	return A.fir == B.fir && A.sec == B.sec;

}

bool operator < (pii A, pii B) {

	if (A.fir != B.fir)	return A.fir < B.fir;

	return A.sec < B.sec;

}

void check(int l, int r) {

	int cnt = 0;

	pii point = p[l] + p[r];

	l = 1, r = n;

	while (l <= r) {

		if (point == p[l] + p[r]) {

			l++, r--;

		} else if (point < p[l] + p[r]) {

			cnt++, r--;

		} else {

			cnt++, l++;

		}

	}

	if (cnt <= k)

		s.insert(point);

}

int main() {

	scanf("%d %d", &n, &k);

	for (int i = 1; i <= n; i++)

		scanf("%d %d", &p[i].fir, &p[i].sec);

	if (n <= k)	return !printf("-1\n");

	sort(p + 1, p + 1 + n);

	for (int i = 1; i <= k + 1; i++)

		for (int j = n - k; j <= n; j++)

			check(i, j);

	printf("%d\n", (int)s.size());

	for (auto i : s)

		printf("%.8lf %.8lf\n", (double)i.fir / 2.0, (double)i.sec / 2.0);

}

巴特西

Codeforces 140F（坐标系点对称）

要点

最新文章

热门文章