2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 I GSM Base Station Identification(暴力，计算几何)

向右看齐 2022-06-08 11:42 146阅读 0赞

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.

[![db061b7fbe6c07cb7ad211a45e04789908e2502f.png][]][db061b7fbe6c07cb7ad211a45e04789908e2502f.png]

For convenience, each cell is denoted by \[i*i*, j*j*\]. The cell covers the origin is denoted by \[00, 00\]. The cell in the east of \[00, 00\] is denoted by \[11, 00\]. The cell in the west of \[00, 00\] is denoted by \[\-1−1, 00\]. The cell in the northeast of \[00, 00\] is denoted by \[00, 11\]. The cell in the southwest of \[00, 00\] is denoted by \[00, \-1−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*x*−*y* plane). Each unit is 11 Km. For example, point (55, 00) in the plane means the location at a distance of 55 Km to the east of the origin. We assume that there are totally 400400 cells, denoted by \[i*i*, j*j*\], i\\ =\\ -9 \\ ... \\ 10*i* = −9 ... 10, j\\ =\\ -9\\ ... \\ 10*j* = −9 ... 10. The base station of cell \[00, 00\] is located at the origin of the Euclidean plane. Each cell has a radius of R*R* = 55 Km, as shown in the following figure.

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

For example, given a location (1010, 00), your program needs to output the cell \[11, 00\], which can cover this location. Specifically, the input and output are:

*  input = (x*x*, y*y*). hhis is a location on the Euclidean plane. This value will not exceed the service area covered by the 400400 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*i*, j*j*\]. One of the 400400 cells that covers location \[i*i*, j*j*\]

### Input Format ###

A list of 1010 locations.

### Output Format ###

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

Please be reminded that there exist a space between coordinates.

#### 样例输入 ####

1 0
    0 15
    2 0
    13 7
    5 5
    10 15
    25 15
    -13 -8
    12 -7
    -10 0

#### 样例输出 ####

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

**题意**：有一个坐标系，每格的长度是5，然后在这个坐标系中有许多边长为5的正六边形，这些正六边形互相连接，没有空隙，每个正六边形都有一个自己的坐标，原点处的正六边形坐标是\[0,0\]，然后每往右一个横坐标+1，每往左一个横坐标-1。然后右上方的纵坐标+1，左下方的纵坐标-1。这样每个正六边形都有属于自己的不同的坐标。现在给你一个坐标系中的坐标，问这个坐标所在的正六边形的坐标是多少。

**思路**：因为正六边形的横坐标和纵坐标的范围都是\[-9,10\]，一共只有400个正六边形，所以我们可以把每一个正六边形都循环一遍，判断当前的这个点是否在该六边形中。现在的问题就是我们怎么判断这个点是否在坐标为\[i,j\]的正六边形中，我们首先可以根据i和j求出该正六边形的中心坐标，仔细观察后可以发现，oy=7.5\*j，ox=5\*sqrt(3)\*i+2.5\*sqrt(3)\*j。然后我们可以根据中心的坐标求出周围六个顶点的坐标，之后我们就可以套用判断一个点是否在一个凸多边形内的模板，如果它在里面，那么当前的i和j就是答案坐标。

#include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <string>  
    #include <cstdlib>  
    #include <cmath>  
    #include <vector>  
    #include <queue>  
    #include <map>  
    #include <algorithm>  
    #include <set>  
    #include <functional>  
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100000007;
    const int MOD = 1e9 + 7;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
    
    struct POINT
    {
    	double x;
    	double y;
    	POINT(double a = 0, double b = 0) { x = a; y = b; } //constructor 
    };
    
    struct LINESEG
    {
    	POINT s;
    	POINT e;
    	LINESEG(POINT a, POINT b) { s = a; e = b; }
    	LINESEG() { }
    };
    
    double multiply(POINT sp, POINT ep, POINT op)
    {
    	return((sp.x - op.x)*(ep.y - op.y) - (ep.x - op.x)*(sp.y - op.y));
    }
    
    bool InsideConvexPolygon(int vcount, POINT polygon[], POINT q) // 可用于三角形！ 
    {
    	POINT p;
    	LINESEG l;
    	int i;
    	p.x = 0; p.y = 0;
    	for (i = 0; i<vcount; i++) // 寻找一个肯定在多边形polygon内的点p：多边形顶点平均值 
    	{
    		p.x += polygon[i].x;
    		p.y += polygon[i].y;
    	}
    	p.x /= vcount;
    	p.y /= vcount;
    
    	for (i = 0; i<vcount; i++)
    	{
    		l.s = polygon[i]; l.e = polygon[(i + 1) % vcount];
    		if (multiply(p, l.e, l.s)*multiply(q, l.e, l.s)<0) /* 点p和点q在边l的两侧，说明点q肯定在多边形外 */
    			break;
    	}
    	return (i == vcount);
    }
    
    void find(int x, int y, int &X, int &Y)
    {
    	double ox, oy;
    	POINT pp[6];
    	for (int i = -9; i <= 10; i++)
    		for (int j = -9; j <= 10; j++)
    		{
    			oy = 7.5*j;
    			ox = 5 * sqrt(3)*i + j*2.5*sqrt(3);
    			pp[0].x = ox;
    			pp[0].y = oy + 5;
    			pp[1].x = ox + 2.5*sqrt(3);
    			pp[1].y = oy + 2.5;
    			pp[2].x = ox + 2.5*sqrt(3);
    			pp[2].y = oy - 2.5;
    			pp[3].x = ox;
    			pp[3].y = oy - 5;
    			pp[4].x = ox - 2.5*sqrt(3);
    			pp[4].y = oy + 2.5;
    			pp[5].x = ox - 2.5*sqrt(3);
    			pp[5].y = oy - 2.5;
    			if (InsideConvexPolygon(6, pp, POINT(x, y)))
    			{
    				X = i;
    				Y = j;
    				return;
    			}
    		}
    }
    
    int main()
    {
    	int x, y;
    	int X, Y;
    	scanf("%d%d", &x, &y);
    	find(x, y, X, Y);
    	printf("[%d,%d]", X, Y);
    	for (int i = 2; i <= 10; i++)
    	{
    		scanf("%d%d", &x, &y);
    		find(x, y, X, Y);
    		printf(", [%d,%d]", X, Y);
    	}
    	printf("\n");
    }

[db061b7fbe6c07cb7ad211a45e04789908e2502f.png]: /images/20220608/58e17f5897224137916c8cef25c14348.png