Source code for submission s1025

Go to diff to previous submission

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.   double 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.   double x1 = v2.x - v1.x;
  36.   double y1 = v2.y - v1.y;
  37.   double x2 = v3.x - v1.x;
  38.   double 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.   double minx, maxx, miny, maxy;
  92.   double minobsah = 100000000000.f;
  93.  
  94.   double 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.     double invlen = 1.f / sqrt(sx * sx + sy * sy);
  105.     sx *= invlen;
  106.     sy *= invlen;
  107.     nx = sy;
  108.     ny = -sx;
  109.     double 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("%lf\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("%lf%lf", &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("%lf %lf\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.  

Diff to submission s1020

fo.cpp

--- c5.s1020.cteam056.fo.cpp.0.fo.cpp
+++ c5.s1025.cteam056.fo.cpp.0.fo.cpp
@@ -14,5 +14,5 @@
 struct vertex
 {
-  float x, y;
+  double x, y;
 };
 
@@ -33,8 +33,8 @@
 bool right(vertex& v1, vertex& v2, vertex& v3)
 {
-  float x1 = v2.x - v1.x;
-  float y1 = v2.y - v1.y;
-  float x2 = v3.x - v1.x;
-  float y2 = v3.y - v1.y;
+  double x1 = v2.x - v1.x;
+  double y1 = v2.y - v1.y;
+  double x2 = v3.x - v1.x;
+  double y2 = v3.y - v1.y;
   return (x1*y2 - x2*y1) < 0.0f;
 }
@@ -89,8 +89,8 @@
 void obdelnik()
 {
-  float minx, maxx, miny, maxy;
-  float minobsah = 100000000000.f;
+  double minx, maxx, miny, maxy;
+  double minobsah = 100000000000.f;
 
-  float sx, sy, nx, ny;
+  double sx, sy, nx, ny;
   for (int i = 0; i < (int)o.size()-1; i++)
   {
@@ -102,10 +102,10 @@
     sx = o[i+1].x - o[i].x;
     sy = o[i+1].y - o[i].y;
-    float invlen = 1.f / sqrt(sx * sx + sy * sy);
+    double invlen = 1.f / sqrt(sx * sx + sy * sy);
     sx *= invlen;
     sy *= invlen;
     nx = sy;
     ny = -sx;
-    float x, y;
+    double x, y;
     for (int j = 0; j < (int)o.size(); j++)
     {
@@ -119,5 +119,5 @@
     minobsah = std::min(minobsah, 2 * (maxx - minx) + 2 * (maxy - miny));
   }
-  printf("%f\n", minobsah);
+  printf("%lf\n", minobsah);
 }
 
@@ -132,5 +132,5 @@
     {
       vertex vnew;
-      scanf("%f%f", &vnew.x, &vnew.y);
+      scanf("%lf%lf", &vnew.x, &vnew.y);
       v.push_back(vnew);
     }
@@ -141,5 +141,5 @@
     for (i = 0; i < vcount; i++)
     {
-      printf("%f %f\n",v[i].x, v[i].y);
+      printf("%lf %lf\n",v[i].x, v[i].y);
     }
     printf("--\n");