2017 ACM-ICPC南宁网络赛: I. GSM Base Station Identification（线性变换）

106 阅读 0 评论 70 点赞

我是靠谱客的博主紧张紫菜，这篇文章主要介绍2017 ACM-ICPC南宁网络赛: I. GSM Base Station Identification（线性变换），现在分享给大家，希望可以做个参考。

https://nanti.jisuanke.com/t/17316

题面有问题直接放链接

题意：

输入一个坐标，问这个坐标所在正六边形的ID，正六边形具分布如下：

题解：

还是看上图，坐标系原点不变，其他所有的点按照一定规则变换到对应正六边形的红点上

例如(1,0)->(sqrt(3), 0)，(0, 1)->(sqrt(3)/2, 1.5)

变换规则为（x和y都要先除以5！）

之后每输入一个点，只要暴力变换后坐标系的每个点即可，如果两个点距离小与等于1直接输出

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
#include<math.h>
int main(void)
{
	int T, i, j, ax, ay;
	double x, y, a, b;
	T = 10;
	while(T--)
	{
		scanf("%lf%lf", &a, &b);
		a /= 5, b /= 5;
		//ax = ay = 1000;
		for(i=-9;i<=10;i++)
		{
			for(j=-9;j<=10;j++)
			{
				x = i*sqrt(3.0)+j*sqrt(3.0)/2;
				y = j*3/2;
				if((x-a)*(x-a)+(y-b)*(y-b)<=1)
					ax = i, ay = j;
			}
		}
		printf("[%d,%d]", ax, ay);
		if(T!=0)
			printf(", ");
	}
	printf("n");
	return 0;
}