首页 > ACM题库 > HDU-杭电 > hdu 2366 Space-计算几何-[解题报告]C++
2014
01-05

hdu 2366 Space-计算几何-[解题报告]C++

Space

问题描述 :

During a programming contest, teams cannot sit close to each other, because then a team might copy the solution of another team. You are given the locations of the teams and the minimum required Euclidian distance between two teams. You have to find the number of pairs of teams that sit too close to each other.

输入:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with two integers n (1 <= n <= 100 000) and d (1 <= d <= 50): the number of teams and the minimum distance between two teams.

n lines with two integers xi (0 <= xi <= 1 000 000 000) and yi (0 <= yi <= 1 000 000 000): the coordinates of the i-th team. No two teams will have the same coordinates.

输出:

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with two integers n (1 <= n <= 100 000) and d (1 <= d <= 50): the number of teams and the minimum distance between two teams.

n lines with two integers xi (0 <= xi <= 1 000 000 000) and yi (0 <= yi <= 1 000 000 000): the coordinates of the i-th team. No two teams will have the same coordinates.

样例输入:

1
6 3
0 0
0 3
2 1
2 3
3 0
3 1

样例输出:

8

 

转载请注明出处:優YoU

http://user.qzone.qq.com/289065406/blog/1302880751

 

大致题意:

一只蚂蚁,只会向左转,现在给出平面上很多个点,求解一种走法,
能使得蚂蚁能经过的点最多,每个顶点该蚂蚁只能经过一次,且所行走的路线不能发生交叉.

 

解题思路:

凸包的入门水题,是凸包的一个变形
网上看到很多人copy别人的,说什么“极坐标排序”,那是Graham Scan Algoruthm的做法!虽然Graham只有O(nlogn) ,但是这题完全没必要用它,因为题目的规模很小,我用卷包裹算法照样0 ms 一次AC 。确实理论上卷包裹的O(n^2)不如Graham快,但是规模这么小的题目是反映不出来的。

Graham能不用就不用,一代码超长超烦,特别是散点集排序。看过算法理论的同学,一般都宁愿用极坐标而不用水平序,但是极坐标排序的比较规则特容易出错。水平排序我没看懂,估计其他菜鸟们也差不多。

 

解题的例图题目已经给出,我就不贴了,反正最终的路线就是螺旋形的。要求从 纵坐标 最小的点作为出发点,这个在输入时顺便找出来,可以节省一点点时间= =

其实无论输入什么样的点集,一定可以走完全部n个点的,这是凸包的性质决定,所以就放手去做了,不用担心走不完的情况

 

唯一注意的是,前面提到过时凸包的变形,是因为螺旋线是不封闭的,凸包是封闭的。要想不封闭很简单,做一个标记就可以了,每构造一个凸包顶点,就标记该点,不再与其连线

当连线完前面n-1个点后,第n个点(最后没被标记的点)就不用再做了,一定是最后一点,输出它就可以了

 

其他细节参见我的程序, 卷包裹算法 百度就有了,这里我就不多说了

 

 

 

 

 

//Memory Time 
//228K   0MS 

#include<iostream>
using namespace std;

const int inf=101;

typedef class
{
	public:
		int x,y;
}point;

/*AB距离平方*/

int distsquare(point A,point B)
{
	return (B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y);
}

/*叉积计算*/

int det(int x1,int y1,int x2,int y2)
{
	return x1*y2-x2*y1;
}

int cross(point A,point B,point C,point D)
{
	return det(B.x-A.x , B.y-A.y , D.x-C.x , D.y-C.y);
}

int main(int i)
{
	int test;
	cin>>test;
	while(test--)
	{
		int n;   //n个点
		cin>>n;
		point* node=new point[n+1];  //n个点坐标
		int* conbag=new int[n+1];    //凸包顶点(根据顶点构造顺序,依次记录node[]下标)
		bool* vist=new bool[n+1];    //标记已作为凸包顶点的点

		/*Input*/

		int min_y=inf;    //最小纵坐标值
		int fi=0;
		for(i=1;i<=n;i++)
		{
			int num;
			cin>>num>>node[i].x>>node[i].y;
			vist[i]=false;

			if(min_y > node[i].y)
			{
				min_y = node[i].y;
				fi=i;
			}
		}
		conbag[1]=fi;  //起点
		conbag[0]=1;  //凸包顶点计数器
		vist[fi]=true;

		/*Structure Convex bag*/

		int pc=1;   //conbag[]指针
		while(true)
		{
			int s=conbag[pc];  //最新的凸包顶点
			int k;    //当前待加入的凸包顶点
			for(i=1;i<=n;i++)   //寻找当前基准向量sk,k取任意没标记的点就可以了
				if(!vist[i])
				{
					k=i;
					break;
				}

			for(i=1;i<=n;i++)   //枚举没标记的点i,计算sk X si的值,寻找最优(最外面的)k点作为凸包顶点
				if(i!=k && !vist[i])
				{
					int temp=cross(node[s],node[k],node[s],node[i]);

					if(temp<0)
						k=i;
					else if(temp==0)
						if(distsquare(node[s],node[k]) > distsquare(node[s],node[i]))  //当k i共线时,距离s近的点优先选取
							k=i;
				}

			conbag[++pc]=k;   //更新凸包顶点
			conbag[0]++;
			vist[k]=true;

			if(n-conbag[0]==1)   //处理完前面n-1个点后 第n个点不再处理
				break;
		}

		cout<<conbag[0]+1<<' ';  //这里输出n也可以的

		fi=0;
		for(i=1;i<=conbag[0];i++)
		{
			cout<<conbag[i]<<' ';   //输出前面n-1个点的同时寻找第n个没标记的点
			if(!vist[i])
				fi=i;
		}
		if(fi)
			cout<<fi<<endl;
		else
			cout<<n<<endl;

		delete node;
		delete conbag;
		delete vist;

	}
	return 0;
}

 

解题转自:http://blog.csdn.net/lyy289065406/article/details/6648614


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count