首页 > 代码库 > UVA10012

UVA10012

2024-08-01 04:51:06   212人阅读

题意：题目意思很简单就是如何安排圆使得他们所用的空间最小，前提是每个圆都必须和底边接触

注意：存在小圆会插在俩个大圆的底下，这样就需要加一个圆心坐标和一个原点记录位置来做特判，令当前放置的圆与前面所有的圆相切求出最大的据原点的距离（这样就可以保证排除圆圆相交的情况），再加上前面的距离即为放置这个新的圆的位置坐标。

 

 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 }
View Code

 

UVA10012


联系
我们