`
Jianquan
  • 浏览: 19832 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

UVa 216 Getting in Line

    博客分类:
  • UVa
阅读更多
题目:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=152
最多只有8个点,枚举所有的排列即可,可以用一个二维数组记录所有的排列以便最后输出。
这道题目是一道水题,但是它的题目描述有点复杂,所以需要一点耐心去读懂题意。有两点可以从题意中得出:不一定要把第一个点当做起点;不必考虑相交的情况。明白这两点就很简单了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define INF 100000000
using namespace std;

struct Point
{
	int x,y;
};

Point p[8];
int a[8],full[50000][8];//a数组用于生成排列,full数组记录所有的排列

double dis(Point a,Point b)
{
	return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
int main()
{
	//freopen("in.txt","r",stdin);
	int i,n,cases=0;
	while(cin>>n&&n)
	{
		cases++;
		for(i=0;i<n;i++)
			cin>>p[i].x>>p[i].y;
		int num=0,min_num=0;
		double min=INF;
		for(i=0;i<n;i++)
			a[i]=i;
		do
		{
			double sum=0;
			for(i=0;i<n-1;i++)
			{
				full[num][i]=a[i];
				sum+=dis(p[a[i]],p[a[i+1]])+16;
			}
			if(sum<min)
			{
				min=sum;
				min_num=num;
			}
			full[num][n-1]=a[n-1];
			num++;
		}while(next_permutation(a,a+n));
		printf("**********************************************************\n");
		printf("Network #%d\n",cases);
		for(i=0;i<n-1;i++)
		{
			int cur=full[min_num][i],next=full[min_num][i+1];
			printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n",p[cur].x,p[cur].y,p[next].x,p[next].y,dis(p[cur],p[next])+16);
		}
		printf("Number of feet of cable required is %.2lf.\n",min);
	}
	return 0;
}

分享到:
评论

相关推荐

    开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip

    开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…

    UVa Online Judge 10944 Accepted Code

    UVa Online Judge 10944 Accepted Code

    UVa Online Judge部分题目代码

    UVa Online Judge是一个著名的在线编程竞赛平台,它提供了大量的算法问题供程序员们挑战,以提升他们的编程技巧和算法理解能力。这个压缩包包含了在UVa平台上部分题目的解答,是学习和参考的好资源。让我们详细了解...

    uva272 uva272 uva272

    标题中的"uva272 uva272 uva272"和描述中的"uva272"指的是UVA(University of Virginia)在线判题系统的第272题,这通常与编程竞赛和算法挑战有关。该题目的标签为"算法",意味着我们需要解决一个与计算机算法设计和...

    uva 200~299 22道题解 均accept

    4. **uva216.cpp**、**uva218.cpp** 和 **uva22.cpp** - 这些分别对应UVA的216、218和22号题目,涵盖的范围广泛,可能包括数值计算、逻辑推理、数据压缩、网络流等不同主题。 5. **uva253.cpp** 和 **uva273.cpp** ...

    uvaoj 习题题目

    在编程学习和竞赛中,UVa Online Judge(简称UVa或OJ)是一个广受欢迎的在线评测系统,它为程序员提供了大量练习题目,涵盖算法、数据结构、数学等多个领域。通过解决这些题目,开发者可以提升自己的编程技能,锻炼...

    UVA_示例代码

    UVA Online Judge(简称UVA OJ)是这个平台的实现,支持多种编程语言,包括C、C++、Java等,用户可以提交代码并实时获取运行结果和评测反馈。 这个名为“UVA_示例代码”的压缩包包含了UVA OJ系统中大量题目的示例...

    开源项目-codingsince1985-UVa.zip

    开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)

    UVA题目大全

    【UVA题目大全】是面向ACM(国际大学生程序设计竞赛)参赛者和算法爱好者的一份宝贵资源。UVA(University of Victoria Algorithm)在线判题系统是世界上最早的在线编程竞赛平台之一,它提供了大量的编程题目供用户...

Global site tag (gtag.js) - Google Analytics