2017 ACM-ICPC 亚洲区（南宁赛区）网络赛-I-GSM Base Station Identification(线性变换)

69 阅读 0 评论 46 点赞

我是靠谱客的博主友好哈密瓜，最近开发中收集的这篇文章主要介绍2017 ACM-ICPC 亚洲区（南宁赛区）网络赛-I-GSM Base Station Identification(线性变换)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

In the Personal Communication Service systems such as GSM (Global System for Mobile Communications), there are typically a number of base stations spreading around the service area. The base stations are arranged in a cellular structure, as shown in the following figure. In each cell, the base station is located at the center of the cell.

For convenience, each cell is denoted by [ $i$ , $j$ ]. The cell covers the origin is denoted by [ $0$ , $0$ ]. The cell in the east of [ $0$ , $0$ ] is denoted by [ $1$ , $0$ ]. The cell in the west of [ $0$ , $0$ ] is denoted by [ $- 1$ , $0$ ]. The cell in the northeast of [ $0$ , $0$ ] is denoted by [ $0$ , $1$ ]. The cell in the southwest of [ $0$ , $0$ ] is denoted by [ $0$ , $- 1$ ]. This notation can be easily generalized, as shown in the above figure.

Now the question is as follows. We have a service area represented by a Euclidean plane (i.e., $x - y$ plane). Each unit is $1$ Km. For example, point ( $5$ , $0$ ) in the plane means the location at a distance of $5$ Km to the east of the origin. We assume that there are totally $400$ cells, denoted by [ $i$ , $j$ ], $i = - 9 . . . 10$ , $j = - 9 . . . 10$ . The base station of cell [ $0$ , $0$ ] is located at the origin of the Euclidean plane. Each cell has a radius of $R$ = $5$ Km, as shown in the following figure.

You are given an input ( $x$ , $y$ ), which indicates a mobile phone’s location. And you need to determine the cell [ $i$ , $j$ ] that covers this mobile phone and can serve this phone call.

For example, given a location ( $10$ , $0$ ), your program needs to output the cell [ $1$ , $0$ ], which can cover this location. Specifically, the input and output are:

input = ( $x$ , $y$ ). hhis is a location on the Euclidean plane. This value will not exceed the service area covered by the $400$ cells. That is, you do not need to handle the exceptional case that the input is out of the boundary of the service area.
output = [ $i$ , $j$ ]. One of the $400$ cells that covers location [ $i$ , $j$ ]

Input Format

A list of $10$ locations.

Output Format

A list of $10$ cells covering the above $10$ locations in the correct order.

Please be reminded that there exist a space between coordinates.

样例输入

样例输出

[0,0], [-1,2], [0,0], [1,1], [0,1], [0,2], [2,2], [-1,-1], [2,-1], [-1,0]

题目来源

2017 ACM-ICPC 亚洲区（南宁赛区）网络赛

题意：给你10个坐标，问你这10个点在哪个正六边形内。

题解：一开始感觉是个超级麻烦的暴力啊，比赛时室友做的这道题，说是线性变换，然而线代早忘得

一干二净了，用线性变换的话就很简单了，将每个正六边形的中心点变换到普通的二维坐标系上就OK了。

我们可以看图找出变换关系式，剩下的就是再正常不过的枚举了。。。。

#include<set>  
#include<map>     
#include<stack>            
#include<queue>            
#include<vector>    
#include<string> 
#include<time.h>
#include<math.h>            
#include<stdio.h>            
#include<iostream>            
#include<string.h>            
#include<stdlib.h>    
#include<algorithm>   
#include<functional>    
using namespace std;            
#define ll long long       
#define inf 1000000000     
#define mod 1000000007             
#define maxn  1360100
#define lowbit(x) (x&-x)            
#define eps 1e-9
int a[15],b[15];
int main(void)
{
	int i,j,t;
	double x,y,xx,yy;
	for(t=1;t<=10;t++)
	{
		scanf("%lf%lf",&x,&y);
		x/=5;y/=5;
		for(i=-9;i<=10;i++)
			for(j=-9;j<=10;j++)
			{
				yy=3.0/2*j;
				xx=i*sqrt(3.0)+j*sqrt(3.0)/2;
				if((xx-x)*(xx-x)+(yy-y)*(yy-y)<=1)
					a[t]=i,b[t]=j;
			}
	}
	for(i=1;i<10;i++)
		printf("[%d,%d], ",a[i],b[i]);
	printf("[%d,%d]n",a[10],b[10]);
	return 0;
}