题目:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=152
最多只有8个点,枚举所有的排列即可,可以用一个二维数组记录所有的排列以便最后输出。
这道题目是一道水题,但是它的题目描述有点复杂,所以需要一点耐心去读懂题意。有两点可以从题意中得出:不一定要把第一个点当做起点;不必考虑相交的情况。明白这两点就很简单了。
最多只有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; }
发表评论
-
UVa 10422 Knights in FEN
2012-09-07 08:40 901题目:http://uva.onlinejudge.org/i ... -
UVa 539 The Settlers of Catan
2012-08-31 22:22 28题目:http://uva.onlinejudge.org/i ... -
UVa 301 Transportation
2012-08-31 22:10 34题目:http://uva.onlinejudge.org/i ... -
UVa 639 Don't Get Rooked
2012-08-30 23:01 811题目:http://uva.onlinejudge.org/i ... -
UVa 10474 Where is the Marble?
2012-08-28 13:45 851题目:http://uva.onlinejudge.org/i ... -
UVa 592 Island of Logic
2012-08-27 11:05 1640题目:http://uva.onlinejudge ... -
UVa 11205 The broken pedometer
2012-08-25 17:28 1049题目:http://uva.onlinejudge.org/i ... -
UVa 131 The Psychic Poker Player
2012-08-24 22:28 874题目:http://uva.onlinejudge.org/i ... -
UVa 729 The Hamming Distance Problem
2012-08-24 12:18 695题目:http://uva.onlinejudge.org/i ... -
Uva 10098 Generating Fast
2012-08-23 15:28 659题目:http://uva.onlinejudge.org/i ... -
UVa 146 ID Codes
2012-08-20 18:46 763题目:http://uva.onlinejudge.org/i ... -
UVa 10167 Birthday Cake
2012-08-16 20:57 604题目:http://uva.onlinejudge.org/i ... -
UVa 10129 Play on Words
2012-08-15 22:49 1126题目:http://uva.onlinejudge.org/i ... -
UVa 10596 Morning Walk
2012-08-14 22:05 879题目:http://uva.onlinejudge.org/i ... -
Uva 10305 Ordering Tasks
2012-08-13 23:40 658题目:http://uva.onlinejudge.org/i ... -
Uva 10004 Bicoloring
2012-08-13 23:34 874题目:http://uva.onlinejudge.org/i ... -
Uva 532 Dungeon Master
2012-08-13 23:29 787题目:http://uva.onlinejudge ... -
Uva 439 Knight Moves
2012-08-11 22:24 656题目:http://uva.onlinejudge.org/i ... -
UVa 784 Maze Exploration
2012-08-11 14:09 825题目:http://uva.onlinejudge.org/i ... -
Uva 572 Oil Deposits
2012-08-11 11:43 745题目:http://uva.onlinejudge.org/i ...
相关推荐
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
UVa Online Judge 10944 Accepted Code
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)
UVA 499 Solution in C/ C++
自己整理的UVa所有题目的PDF题面,可根据目录中的Volume快速跳转(与UVa官网一致)。 题目共4965题,PDF共8380页,可能会出现打开较慢的问题。 关于某个题目所在位置的判断方法: 题号除了后两位的其他数字构成...
UVA109的题解,经测试完全正确,还附有题解。
uva272
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传