2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 GSM Base Station Identification 线性变换||计算几何

68 阅读 0 评论 45 点赞

我是靠谱客的博主曾经小懒虫，最近开发中收集的这篇文章主要介绍2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 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 亚洲区（南宁赛区）网络赛

题意：

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

思路：

所谓线性变换：通俗的理解就是,A集合中的每一个元素,经过某种规则变换，总有非空集合B中一个确定元素和他对应.

那么关于这个题目,我们对于每个正六边形的坐标需要映射到在整个坐标系（集合B中的坐标）的坐标（正六边形的中心）.

通过上图可以很简单的算出: 正六边形中心（ox,oy）。

ox=5*sqrt(3)*i+2.5*sqrt(3)*j

oy=7.5*j。

知道这个坐标,因为最多400个多边形,我们可以枚举每个多边形,判断给定点在不在多边形内（直接判断中心到给定

点的距离即可）。

#include<bits/stdc++.h>

using namespace std;
const double base = sqrt(3.0);
const int maxn = 10+5;
bool judge(double x,double y,double xx,double yy)
{
	double dis = (x - xx)*(x - xx) + (y - yy)*(y - yy);
	if(dis <= 25)
	return 1;
	return 0;
}
void solve(double x,double y)
{
	for(int i = -9;i <= 10;++i)
	{
		for(int j = -9;j <= 10;++j)
		{
			double ox = 5*base*i+2.5*base*j;
			double oy = 7.5*j;
			if(judge(x,y,ox,oy))
			printf("[%d,%d]",i,j);
		}
	}
}
int main()
{
	double x,y;
	for(int _ = 1;_ <= 10;_++)
	{
		scanf("%lf %lf",&x,&y);
		solve(x,y);
		if(_ != 10)
		printf(", ");
		else
		puts("");
	}
	return 0;
}

当然,麻烦一点的做法是用计算几何模板,还是要算出中心坐标,进而得到正六边形的六个顶点坐标,然后套模板判断关系.

/*
射线法:判断一个点是在多边形内部，边上还是在外部,时间复杂度为O(n)；
射线法可以正确用于凹多边形；
射线法是使用最广泛的算法，这是由于相比较其他算法而言，它不但可以正
确使用在凹多边形上，而且不需要考虑精度误差问题。该算法思想是从点出
发向右水平做一条射线，计算该射线与多边形的边的相交点个数，当点不在
多边形边上时，如果是奇数，那么点就一定在多边形内部，否则，在外部。
*/
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 2010;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
//
struct point
{
    double x, y;
    point(double x=0, double y=0) : x(x), y(y){}
    friend point operator - (const point& p1, const point& p2)
    {
        return point(p1.x-p2.x, p1.y-p2.y);
    }
    friend double operator ^ (const point& p1, const point& p2)
    {
        return p1.x*p2.y - p1.y*p2.x;
    }
};
//
struct Segment
{
    point s, e;
};
//
///判断一个double类型的数是  0  <0  >0;
int Sign(double x)
{
    if( fabs(x) < eps )return 0;
    if(x > 0)return 1;
    return -1;
}
//
///判断o在ab的哪边；0:o在直线ab上; >0:在左边; <0:在右边；
double cross(point o, point a, point b)
{
    return ((a-o)^(b-o));
}
//
///已知abc三点在一条直线上，判断点a是否在线段bc之间；<=0:在   >0:不在;
int Between(point a, point b, point c)
{
    if(fabs(b.x-c.x) > fabs(b.y-c.y))
        return Sign(min(b.x, c.x)-a.x)*Sign(max(b.x, c.x)-a.x);
    else
        return Sign(min(b.y, c.y)-a.y)*Sign(max(b.y, c.y)-a.y);
}
//
///判断点p0和线段S上，<=0:在，1:不在；
int PointOnSegment(point p0, Segment S)
{
    if(Sign(cross(S.s, S.e, p0)) == 0)
        return Between(p0, S.s, S.e);
    return 1;
}
//
///求线段a和线段b的交点个数；
int SegmentCross(Segment a, Segment b)
{
    double x1 = cross(a.s, a.e, b.s);
    double x2 = cross(a.s, a.e, b.e);
    double x3 = cross(b.s, b.e, a.s);
    double x4 = cross(b.s, b.e, a.e);

    if(Sign(x1*x2)<0 && Sign(x3*x4)<0) return 1;
    if((Sign(x1)==0 && Between(b.s, a.s, a.e)<=0) ||
       (Sign(x2)==0 && Between(b.e, a.s, a.e)<=0) ||
       (Sign(x3)==0 && Between(a.s, b.s, b.e)<=0) ||
       (Sign(x4)==0 && Between(a.e, b.s, b.e)<=0))
       return 2;
    return 0;
}
//
///判断点p0与含有n个节点的多边形的位置关系，p数组是顶点集合；
///返回0:边上或顶点上,    1:外面,   -1:里面;
int PointInPolygon(point p0, point p[], int n)
{
    Segment L, S;
    point temp;
    L.s = p0, L.e = point(INF, p0.y);///以p0为起点的射线L；

    int counts = 0;
    p[n] = p[0];

    for(int i=1; i<=n; i++)
    {
        S.s = p[i-1], S.e = p[i];

        if(PointOnSegment(p0, S) <= 0) return 0;
        if(S.s.y == S.e.y) continue;///和射线平行；

        if(S.s.y > S.e.y) temp = S.s;
        else temp = S.e;

        if(PointOnSegment(temp, L) == -1)
            counts ++;
        else if(SegmentCross(L, S) == 1)
            counts ++;
    }
    if(counts%2) return -1;
    return 1;
}

void find(int x, int y, int &X, int &Y)  
{  
    double ox, oy;  
    point pp[7];  
    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 (PointInPolygon(point(x,y),pp,6) <= 0)  
            {  
                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");  
}