Source code for submission s1020

fo.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4. #include <string.h>
  5.  
  6. #include <string>
  7. #include <map>
  8. #include <vector>
  9. #include <algorithm>
  10.  
  11. int i, j, k;
  12. int i2, j2, k2;
  13.  
  14. struct vertex
  15. {
  16.   float x, y;
  17. };
  18.  
  19. bool cmpv(const vertex &a, const vertex &b)
  20. {
  21.   if (a.x < b.x)
  22.     return true;
  23.   if (a.x == b.x && a.y > b.y)
  24.     return true;
  25.  
  26.   return false;
  27. }
  28.  
  29. int vcount;
  30. std::vector<vertex> v;
  31. std::vector<vertex> o;
  32.  
  33. bool right(vertex& v1, vertex& v2, vertex& v3)
  34. {
  35.   float x1 = v2.x - v1.x;
  36.   float y1 = v2.y - v1.y;
  37.   float x2 = v3.x - v1.x;
  38.   float y2 = v3.y - v1.y;
  39.   return (x1*y2 - x2*y1) < 0.0f;
  40. }
  41.  
  42. void obalka()
  43. {
  44.   o.clear();
  45.   if (vcount > 0)
  46.     o.push_back(v[0]);
  47.   if (vcount > 1)
  48.     o.push_back(v[1]);
  49.  
  50.   for (i = 2; i < vcount; i++)
  51.   {
  52.     while (!right(o[o.size()-2], o[o.size()-1], v[i]))
  53.     {
  54.       //printf("vyhazuju %0.1f %0.1f\n", o.back().x, o.back().y);
  55.       o.pop_back();
  56.       if (o.size() == 1)
  57.       {
  58. 	break;
  59.       }
  60.     }
  61.     o.push_back(v[i]);
  62.       //printf("pridavam %0.1f %0.1f\n", o.back().x, o.back().y);
  63.   }
  64.  
  65.   for (i = vcount-1; i >= 0; i--)
  66.   {
  67.     while (!right(o[o.size()-2], o[o.size()-1], v[i]))
  68.     {
  69.      // printf("vyhazuju %0.1f %0.1f\n", o.back().x, o.back().y);
  70.       o.pop_back();
  71.       if (o.size() == 1)
  72.       {
  73. 	break;
  74.       }
  75.     }
  76.     o.push_back(v[i]);
  77.       //printf("pridavam %0.1f %0.1f\n", o.back().x, o.back().y);
  78.   }
  79.  
  80.   /*
  81.   for (int i = 0; i < (int)o.size(); i++)
  82.   {
  83.     printf("o: %.1f %.1f\n", o[i].x, o[i].y);
  84.   }
  85.   printf("///\n");
  86.    */
  87. }
  88.  
  89. void obdelnik()
  90. {
  91.   float minx, maxx, miny, maxy;
  92.   float minobsah = 100000000000.f;
  93.  
  94.   float sx, sy, nx, ny;
  95.   for (int i = 0; i < (int)o.size()-1; i++)
  96.   {
  97.     minx = 10000000000.f;
  98.     miny = 10000000000.f;
  99.     maxx = -10000000000.f;
  100.     maxy = -10000000000.f;
  101.  
  102.     sx = o[i+1].x - o[i].x;
  103.     sy = o[i+1].y - o[i].y;
  104.     float invlen = 1.f / sqrt(sx * sx + sy * sy);
  105.     sx *= invlen;
  106.     sy *= invlen;
  107.     nx = sy;
  108.     ny = -sx;
  109.     float x, y;
  110.     for (int j = 0; j < (int)o.size(); j++)
  111.     {
  112.       x = o[j].x * sx + o[j].y * sy;
  113.       y = o[j].x * nx + o[j].y * ny;
  114.       minx = std::min(x, minx);
  115.       miny = std::min(y, miny);
  116.       maxx = std::max(x, maxx);
  117.       maxy = std::max(y, maxy);
  118.     }
  119.     minobsah = std::min(minobsah, 2 * (maxx - minx) + 2 * (maxy - miny));
  120.   }
  121.   printf("%f\n", minobsah);
  122. }
  123.  
  124. /* ------------------------------- */
  125. int main()
  126. {
  127.   while (scanf("%d", &vcount) == 1)
  128.   {
  129.     v.clear();
  130.     v.reserve(vcount);
  131.     for (i = 0; i < vcount; i++)
  132.     {
  133.       vertex vnew;
  134.       scanf("%f%f", &vnew.x, &vnew.y);
  135.       v.push_back(vnew);
  136.     }
  137.  
  138.     std::sort(v.begin(), v.end(), cmpv);
  139.  
  140.     /*
  141.     for (i = 0; i < vcount; i++)
  142.     {
  143.       printf("%f %f\n",v[i].x, v[i].y);
  144.     }
  145.     printf("--\n");
  146.     */
  147.  
  148.  
  149.     obalka();
  150.     obdelnik();
  151.   }
  152.  
  153.   return 0;
  154. }
  155.