Source code for submission s907

Go to diff to previous submission

fo.cpp

  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <cstdio>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <climits>
  8.  
  9. typedef unsigned int uint;
  10. typedef long double number;
  11.  
  12. struct point {
  13. number x, y;
  14.  
  15. point():
  16. x(0.0),
  17. y(0.0) {
  18. }
  19.  
  20. point(number x, number y):
  21. x(x),
  22. y(y) {
  23. }
  24. };
  25.  
  26. bool operator== (const point& a, const point& b) {
  27. return a.x == b.x && a.y == b.y;
  28. }
  29.  
  30. bool operator!= (const point& a, const point& b) {
  31. return a.x != b.x || a.y != b.y;
  32. }
  33.  
  34. bool operator< (const point& a, const point& b) {
  35. return a.x == b.x ? a.y < b.y : a.x < b.x;
  36. }
  37.  
  38. bool operator> (const point& a, const point& b) {
  39. return a.x == b.x ? a.y > b.y : a.x > b.x;
  40. }
  41.  
  42. number cross(const point& a, const point& b, const point& c) {
  43. return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  44. }
  45.  
  46. number dist(const point& a, const point& b) {
  47. number dx = b.x - a.x;
  48. number dy = b.y - a.y;
  49. if (dx == 0.0 && dy == 0.0)
  50. return 0.0;
  51.  
  52. return sqrt( dx * dx + dy * dy );
  53. }
  54.  
  55. point center(const point& p1, const point& p2, const point& far) {
  56. if (p1.x == p2.x)
  57. return point(p1.x, far.y);
  58. if (p1.y == p2.y)
  59. return point(far.x, p1.y);
  60.  
  61. number k = (p2.y - p1.y) / (p2.x - p1.x);
  62. number kperp = (p1.x - p2.x) / (p2.y - p1.y);
  63. number d = p2.y - k * p2.x;
  64. number dperp = far.y - kperp * far.x;
  65. number xint = (d - dperp) / (kperp - k);
  66. number yint = kperp * xint + dperp;
  67. return point(xint, yint);
  68. }
  69.  
  70. void obtainconvexhull(std::vector<point>& hull, std::vector<point>& points) {
  71. std::sort(points.begin(), points.end());
  72. hull.push_back(points[0]);
  73. uint last_added = 0;
  74. uint ref;
  75.  
  76. do
  77. {
  78. ref = 0;
  79. for (uint j = 0; j < points.size(); j++)
  80. {
  81. int wedge = cross(hull[last_added], points[ref], points[j]);
  82. if (points[ref] == hull[last_added] || wedge < 0)
  83. ref = j;
  84. }
  85. if (ref != 0)
  86. {
  87. hull.push_back(points[ref]);
  88. points.erase(points.begin()+ref);
  89. last_added++;
  90. }
  91. }
  92. while (ref != 0);
  93. }
  94.  
  95. number getminwidth(std::vector<point>& polygon) {
  96. uint aux = polygon.size();
  97. number minwidthoverall = INT_MAX; // WHAT?
  98. point firstmaxc;
  99. bool is_firstmaxc = false;
  100. for (uint i = 0; i < aux; i++)
  101. {
  102. number maxwidthforoneside = 0.0;
  103. point maxc;
  104.  
  105. if (is_firstmaxc && polygon[i] == firstmaxc)
  106. break;
  107.  
  108. point lineA = polygon[i];
  109. point lineB = polygon[(i + 1) % aux];
  110.  
  111. for (uint j = 0; j < aux; j++)
  112. if (polygon[j] != lineA && polygon[j] != lineB)
  113. {
  114. point c = center(lineA, lineB, polygon[j]);
  115. number d = dist(c, polygon[j]);
  116. //~ if (d > 21213212)
  117. //~ printf("bad: c.x=%Lf, c.y=%Lf, pol[j].x=%Lf, pol[j].y=%Lf\n", c.x, c.y, polygon[j].x, polygon[j].y);
  118. if (maxwidthforoneside < d)
  119. {
  120. maxwidthforoneside = d;
  121. maxc = polygon[j];
  122. }
  123. }
  124. if (!is_firstmaxc)
  125. firstmaxc = maxc;
  126.  
  127. number left = 0.0; // product < 0
  128. number right = 0.0; // product > 0
  129. point ab = center(lineA, lineB, maxc);
  130. for (uint j = 0; j < aux; j++)
  131. {
  132. if (maxc == polygon[j])
  133. continue;
  134.  
  135. point c = center(maxc, ab, polygon[j]);
  136. number d = dist(c, polygon[j]);
  137. number product = cross(maxc, ab, polygon[j]);
  138. if (product < 0)
  139. left = std::max(left, d);
  140. if (product > 0)
  141. right = std::max(right, d);
  142. }
  143.  
  144. //~ printf("current minwidth: %Lf\n", minwidthoverall);
  145. //~ printf("maxwidthforoneside: %Lf, left: %Lf, right: %Lf\n", maxwidthforoneside, left, right);
  146. minwidthoverall = std::min(minwidthoverall, maxwidthforoneside * 2 + (left + right) * 2);
  147. //~ printf("new minwidth: %Lf\n\n", minwidthoverall);
  148. }
  149. return minwidthoverall;
  150. }
  151.  
  152. int main() {
  153. int vertices;
  154.  
  155. while (true)
  156. {
  157. if (1 != scanf("%d", &vertices))
  158. break;
  159.  
  160. std::vector<point> polygon;
  161. while (vertices--)
  162. {
  163. int x, y;
  164. scanf("%d %d", &x, &y);
  165. polygon.push_back(point(number(x), number(y)));
  166. }
  167.  
  168. std::vector<point> convexhull;
  169. obtainconvexhull(convexhull, polygon);
  170. number answertoeverything = getminwidth(convexhull);
  171.  
  172. printf("%Lf\n", answertoeverything);
  173. }
  174.  
  175. return 0;
  176. }
  177.  

Diff to submission s900

fo.cpp

--- c5.s900.cteam063.fo.cpp.0.fo.cpp
+++ c5.s907.cteam063.fo.cpp.0.fo.cpp
@@ -96,8 +96,14 @@
         uint aux = polygon.size();
         number minwidthoverall = INT_MAX; // WHAT?
+        point firstmaxc;
+        bool is_firstmaxc = false;
         for (uint i = 0; i < aux; i++)
         {
                 number maxwidthforoneside = 0.0;
                 point maxc;
+                
+                if (is_firstmaxc && polygon[i] == firstmaxc)
+                        break;
+                
                 point lineA = polygon[i];
                 point lineB = polygon[(i + 1) % aux];
@@ -116,4 +122,6 @@
                                 }
                         }
+                if (!is_firstmaxc)
+                        firstmaxc = maxc;
                 
                 number left = 0.0; // product < 0