AtCoder Beginner Contest 226 D - Teleportation

题意

题解

公理1：最小化操作次数。

公理2：巫师可以无限次跳跃，跳跃次数与输出的答案无关。

性质1（公理1、2）：跳跃(a,b)可被优化为(a/gcd(a,b),b/gcd(a,b))，且答案不会变劣。

前置知识1：set>可自动去重，输出set.size()即可得到答案数量。

性质2：可以O（n^2）。

公理3：巫师在能跳到一个地方的同时，也要能够跳回去（-x，-y）。

答案1（前置知识1、性质1、性质2）：对于每两个坐标，得到两坐标的差值，除以gcd，得到一个pair(deltaX,deltaY)，存到set中。

答案2（公理2、公理3）：答案为2*set.size()。

#include
#include
#include
#include
using namespace std;
const int MAXN = 1000;
int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a%b);
}

struct Point {
	int x, y;
}p[MAXN];

int main() {
	int n;
	scanf("%d", &n);

	set> pSet;
	for (int i = 1; i <= n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		p[i].x = x;
		p[i].y = y;
		
	}

	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			Point point1 = p[i];
			Point point2 = p[j];
			int x = point1.x - point2.x;
			int y = point1.y - point2.y;
			int gcdVal = gcd(x, y);
			if (gcdVal != 0) {
				x /= gcdVal;
				y /= gcdVal;
			}
			pSet.insert({ x,y });
		}
	}

	cout << pSet.size()*2 << endl;

	return 0;
}

TRANSLATE with

Bing Webmaster Portal