Don't like ads? PRO users don't see any ads ;-)
Guest

This takes the Cake

By: Sharod on Jun 20th, 2012  |  syntax: C++  |  size: 3.19 KB  |  hits: 14  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #pragma comment (linker,"/STACK:16777216")
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <map>
  7. #include <queue>
  8. #include <stack>
  9. #include <vector>
  10. #include <deque>
  11. #include <functional>
  12. #include <string>
  13.  
  14. using namespace std;
  15.  
  16. const int inf = 2147483647;
  17. const double pi = 2 * acos ( 0.0 );
  18. const double eps = 1e-11;
  19.  
  20. int MIN ( int &a, int &b )
  21. {
  22.         if ( a < b ) return a;
  23.         return b;
  24. }
  25. int MAX ( int &a, int &b )
  26. {
  27.         if ( a > b ) return a;
  28.         return b;
  29. }
  30.  
  31. double sres , lres , dif , tarea;
  32.  
  33. struct p {
  34.         double x , y;
  35. }pp[8];
  36.  
  37. bool end_check() {
  38.         if( pp[0].x==0 && pp[0].y==0 && pp[2].x==0 && pp[2].y == 0 && pp[4].x == 0 && pp[4].y==0 && pp[6].x==0 && pp[6].y == 0 )
  39.                 return true;
  40.         return false;
  41. }
  42.  
  43. double quad_area( p a , p b , p c , p d ) {
  44.         double a1 , a2 , r;
  45.         a1 = a.x*b.y + b.x*c.y + c.x*d.y + d.x*a.y;
  46.         a2 = a.y*b.x + b.y*c.x + c.y*d.x + d.y*a.x;
  47.         r = 0.5 * ( a1 - a2 );
  48.         return r;
  49. }
  50.  
  51. double tri_area( p a , p b , p c ) {
  52.         double a1 , a2 , r;
  53.         a1 = a.x*b.y + b.x*c.y + c.x*a.y;
  54.         a2 = a.y*b.x + b.y*c.x + c.y*a.x;
  55.         r = 0.5 * ( a1 - a2 );
  56.         return r;
  57. }
  58.  
  59. void get_result() {
  60.         int i , j , k;
  61.         double a , b , d , mx , mn;
  62.         for( i = 0 ; i < 8 ; i++ ) {
  63.                 if( i == 0 || i == 2 || i == 4 || i == 6 ) {
  64.                         //printf( "Hello\n" );
  65.                         for( j = 3 ; j <= 5 ; j++ ) {
  66.                                 k = ( i + j ) % 8;
  67.                                 if( j == 3 ) {
  68.                                         a = tri_area( pp[i] , pp[k-1] , pp[k] );
  69.                                         b = tarea - a;
  70.                                 }
  71.                                 else if( j == 4 ) {
  72.                                         a = tri_area( pp[i] , pp[k-2] , pp[k] );
  73.                                         b = tarea - a;
  74.                                 }
  75.                                 else {
  76.                                         a = tri_area( pp[i] , pp[k] , pp[k+1] );
  77.                                         b = tarea - a;
  78.                                 }
  79.                                 if( a > b + eps )
  80.                                         mx = a , mn = b;
  81.                                 else
  82.                                         mx = b , mn = a;
  83.                                 if( ( mx - mn ) < dif )
  84.                                         dif = mx - mn , lres = mx , sres = mn;
  85.                         }
  86.                 }
  87.                 else {
  88.                         for( j = 2 ; j <= 6 ; j++ ) {
  89.                                 if( j == 2 || j == 3 ) {
  90.                                         if( j == 2 ) k = 1;
  91.                                         else k = 2;
  92.                                         a = tri_area( pp[i] , pp[(i+j)%8-k] , pp[(i+j)%8] );
  93.                                         b = tarea - a;
  94.                                 }
  95.                                 else if( j == 4 ) {
  96.                                         a = quad_area( pp[i] , pp[(i+1)%8] , pp[(i+3)%8] , pp[(i+j)%8] );
  97.                                         b = tarea - a;
  98.                                 }
  99.                                 else {
  100.                                         if( j == 6 ) k = 1;
  101.                                         else k = 2;
  102.                                         a = tri_area( pp[i] , pp[(i+j)%8] , pp[(i+j)%8+k] );
  103.                                         b = tarea - a;
  104.                                 }
  105.                                 if( a > b + eps )
  106.                                         mx = a , mn = b;
  107.                                 else
  108.                                         mx = b , mn = a;
  109.                                 if( ( mx - mn ) < dif )
  110.                                         dif = mx - mn , lres = mx , sres = mn;
  111.                         }
  112.                 }
  113.         }
  114. }
  115.  
  116. int main ()
  117. {
  118.         int cn = 0;
  119.         //freopen ( "input.txt", "r", stdin );
  120.         //freopen ( "output.txt", "w", stdout );
  121.         while( scanf( "%lf%lf%lf%lf%lf%lf%lf%lf" , &pp[0].x,&pp[0].y,&pp[2].x,&pp[2].y,&pp[4].x,&pp[4].y,&pp[6].x,&pp[6].y) != EOF ) {
  122.                 if( end_check() ) break;
  123.                 dif = inf;
  124.                 pp[1].x = ( pp[0].x + pp[2].x ) / 2;
  125.                 pp[1].y = ( pp[0].y + pp[2].y ) / 2;
  126.                 pp[3].x = ( pp[2].x + pp[4].x ) / 2;
  127.                 pp[3].y = ( pp[2].y + pp[4].y ) / 2;
  128.                 pp[5].x = ( pp[4].x + pp[6].x ) / 2;
  129.                 pp[5].y = ( pp[4].y + pp[6].y ) / 2;
  130.                 pp[7].x = ( pp[6].x + pp[0].x ) / 2;
  131.                 pp[7].y = ( pp[6].y + pp[0].y ) / 2;
  132.                 tarea = quad_area(pp[0],pp[2],pp[4],pp[6]);
  133.                 //printf("%lf\n", tarea);
  134.                 get_result();
  135.                 printf( "Cake %d: %.3lf %.3lf\n" , ++cn , sres + eps , lres + eps );
  136.         }
  137.         return 0;
  138. }