首页 > 代码库 > UVA10012
UVA10012
题意:题目意思很简单就是如何安排圆使得他们所用的空间最小,前提是每个圆都必须和底边接触
注意:存在小圆会插在俩个大圆的底下,这样就需要加一个圆心坐标和一个原点记录位置来做特判,令当前放置的圆与前面所有的圆相切求出最大的据原点的距离(这样就可以保证排除圆圆相交的情况),再加上前面的距离即为放置这个新的圆的位置坐标。
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cctype> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <map> 9 #include <stack>10 #include <set>11 #include <vector>12 #include <algorithm>13 #include <iostream>14 using namespace std;15 typedef long long ll;16 #define PI acos( -1.0 )17 const double E = 1e-8;18 double a[15], b[15], d[15];19 int mark[15];20 double ans;21 int n;22 23 void cheak( int x )24 {25 d[x] = b[x];26 for( int i = x-1; i >= 0; --i )27 {28 double x1 = b[i] - b[x];29 double x2 = b[i] + b[x];30 x1 = d[i] + sqrt( x2*x2 - x1*x1 );31 if( x1 > d[x] )32 d[x] = x1;33 }34 }35 36 void dfs( int x, double num )37 {38 if( num > ans )39 return;40 if( x == n )41 {42 double k = b[0];43 num += b[x-1];44 for( int i = 0; i < n; ++i )45 if( num < b[i] + d[i] )46 num = b[i] + d[i];47 for( int i = 1; i < n; ++i )//检查是否存在一点边长比前面所用的长度要大48 if( k < b[i] - d[i] )49 k = b[i] - d[i];50 num += k;51 if( num < ans )52 ans = num;53 return;54 }55 for( int i = 0; i < n; ++i )56 if( !mark[i] )57 {58 mark[i] = 1;59 b[x] = a[i];60 cheak( x );61 dfs( x+1, d[x] );62 mark[i] = 0;63 }64 }65 66 int main()67 {68 int T;69 scanf( "%d", &T );70 while( T-- )71 {72 scanf( "%d", &n );73 for( int i = 0; i < n; ++i )74 scanf( "%lf", &a[i] );75 ans = 0x7fffffffffff;76 for( int i = 0; i < n; ++i )77 {78 memset( mark, 0, sizeof( mark ) );79 mark[i] = 1;80 b[0] = a[i];81 d[0] = 0;82 dfs( 1, 0 );83 }84 printf( "%.3lf\n", ans );85 }86 return 0;87 }
UVA10012
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。