fork download
copy 
  1. /***********Template Starts Here***********/
  2. #include <bits/stdc++.h>
  3.  
  4. #define pb push_back
  5. #define nl puts ("")
  6. #define sp printf ( " " )
  7. #define phl printf ( "hello\n" )
  8. #define ff first
  9. #define ss second
  10. #define POPCOUNT __builtin_popcountll
  11. #define RIGHTMOST __builtin_ctzll
  12. #define LEFTMOST(x) (63-__builtin_clzll((x)))
  13. #define MP make_pair
  14. #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
  15. #define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
  16. #define CLR(x,y) memset(x,y,sizeof(x))
  17. #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
  18. #define MIN(a,b) ((a)<(b)?(a):(b))
  19. #define MAX(a,b) ((a)>(b)?(a):(b))
  20. #define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
  21. #define SQ(x) ((x)*(x))
  22. #define ABS(x) ((x)<0?-(x):(x))
  23. #define FABS(x) ((x)+eps<0?-(x):(x))
  24. #define ALL(x) (x).begin(),(x).end()
  25. #define LCM(x,y) (((x)/gcd((x),(y)))*(y))
  26. #define SZ(x) ((vlong)(x).size())
  27. #define NORM(x) if(x>=mod)x-=mod;
  28.  
  29. using namespace std;
  30.  
  31. typedef long long vlong;
  32. typedef vector<int> vi;
  33.  
  34. const vlong inf = 2147383647;
  35. const double eps = 1e-11;
  36.  
  37. struct polygon {
  38.     vlong h;
  39.     double x, y;
  40.  
  41.     void init ( vlong _h ) {
  42.         h = _h;
  43.         calcY();
  44.         calcX();
  45.     }
  46.     void calcY (){
  47.         y = h / ( 2 + sqrt ( 2 ) );
  48.     }
  49.     void calcX() {
  50.         x = sqrt ( 2 * y * y );
  51.     }
  52. }pol[10];
  53.  
  54. vi arr;
  55.  
  56. double center[10];
  57.  
  58. int main () {
  59.     int kase, cnt = 0;
  60.     scanf ( "%d", &kase );
  61.  
  62.     while ( kase-- ) {
  63.         int n;
  64.         scanf ( "%d", &n );
  65.  
  66.         arr.clear();
  67.  
  68.         double mxh = -1;
  69.         FOR(i,0,n-1){
  70.             arr.pb ( i );
  71.             int t;
  72.             scanf ( "%d", &t );
  73.             pol[i].init(t);
  74.             if ( t > mxh ) mxh = t;
  75.         }
  76.  
  77.         double res = inf * inf;
  78.  
  79.         do {
  80.             double curWidth = 0;
  81.             curWidth = pol[arr[0]].y * 2 + pol[arr[0]].x;
  82.             center[0] = curWidth / 2;
  83.  
  84.             FOR(iron,1,n-1){ ///Try to fit this polygon as close as possible
  85.                 ///Try to push center of this pol near a pol, then check for conflict
  86.                 int b = arr[iron];
  87.                 center[iron] = ( pol[b].y * 2 + pol[b].x ) / 2; ///Empty
  88.                 FOR(joker,0,iron-1){
  89.                     int a = arr[joker];
  90.                     if ( pol[a].h > pol[b].h + eps && pol[a].y > pol[b].y + pol[b].x + eps ) {
  91.                         ///A is bigger than B
  92.                         double d = 2 * pol[b].y + 1.5 * pol[b].x;
  93.                         double probableCenter = center[joker] + pol[a].x / 2 + d;
  94.  
  95.                         if ( probableCenter > center[iron] + eps ) {
  96.                             center[iron] = probableCenter;
  97.                         }
  98.                     }
  99.                     else if ( pol[b].h > pol[a].h + eps && pol[b].y > pol[a].y + pol[a].x + eps ) {
  100.                         ///B is bigger than A
  101.  
  102.                         double d = pol[a].x / 2 + pol[a].y + pol[a].x + pol[a].y + pol[b].x / 2;
  103.                         double probableCenter = center[joker] + d;
  104.  
  105.                         if ( probableCenter > center[iron] + eps ) {
  106.                             center[iron] = probableCenter;
  107.                         }
  108.                     }
  109.                     else {
  110.                         double d = pol[a].x / 2 + pol[a].y + pol[b].y + pol[b].x / 2;
  111.                         double probableCenter = center[joker] + d;
  112.                         if ( probableCenter > center[iron] + eps ) {
  113.                             center[iron] = probableCenter;
  114.                         }
  115.                     }
  116.                 }
  117.                 double tempWidth = center[iron] + pol[b].x / 2 + pol[b].y;
  118.                 if ( tempWidth > curWidth + eps ) curWidth = tempWidth;
  119.             }
  120.  
  121.             double vol = 8 * mxh * curWidth;
  122.  
  123.             if ( vol + eps < res ) res = vol;
  124.         }while ( next_permutation ( ALL(arr) ) );
  125.  
  126.         printf ( "Case %d: %.10lf\n", ++cnt, res + eps );
  127.     }
  128.  
  129.     return 0;
  130. }
  131.  
Runtime error #stdin #stdout 0s 3456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kphGx5
Blog UVa 12835 - Fitting Pipes Again
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!