Source code for submission s1061

Go to diff to previous submission

fo.cpp

  1. #include <iostream>
  2. #include <set>
  3. #include <stdio.h>
  4. #include <utility>
  5. #include <map>
  6. #include <string>
  7. #include <sstream>
  8. #include <algorithm>
  9. #include <iterator>
  10. #include <vector>
  11. #include <cmath>
  12. using namespace std;
  13.  
  14. typedef pair<int,int> point;
  15. typedef vector<pair<int,int> >::iterator vp_it;
  16.  
  17. bool counterclockwise(const point &A, const point &B, const point &C) {
  18. return ((B.first - A.first)*(C.second-A.second)-(B.second-A.second)*(C.first-A.first)) > 0;
  19. }
  20. bool clockwise(const point &A, const point &B, const point &C) {
  21. return ((B.first - A.first)*(C.second-A.second)-(B.second-A.second)*(C.first-A.first)) < 0;
  22. }
  23.  
  24. double distance(const point &A, const point &B, const point &C) {
  25. return ((B.first - A.first)*(C.second - A.second) - (C.first - A.first)*(B.second -A.second))
  26. / sqrt((B.first - A.first)*(B.first - A.first) + (B.second - A.second)*(B.second - A.second));
  27. }
  28.  
  29. point normpoint(const point &A, const point &B) {
  30. point x = make_pair(B.first - A.first, B.second - A.second);
  31. point nx = make_pair(-x.second, x.first);
  32. return nx;
  33. }
  34.  
  35. point add(const point &A, const point &B) {
  36. return make_pair(A.first + B.first, A.second + B.second);
  37. }
  38.  
  39. bool EQ(double a, double b)
  40. {
  41. if (abs(a-b) < 10e-6) return true;
  42. return false;
  43. }
  44.  
  45. vector<point> convex_hull(vector<point> &Ps) {
  46. sort(Ps.begin(),Ps.end());
  47. if (Ps.size() < 3) return Ps;
  48. vector<point> lower,upper;
  49. lower.push_back(Ps.front());
  50. upper.push_back(Ps.front());
  51.  
  52. for (vp_it p_it = Ps.begin()+1;p_it != Ps.end(); ++p_it) {
  53. vp_it it = lower.end()-1;
  54. for (;it != lower.begin();--it)
  55. if (it == lower.begin() || counterclockwise(*(it-1),*it,*p_it))
  56. break;
  57. lower.erase(it+1,lower.end());
  58. lower.push_back(*p_it);
  59.  
  60. it = upper.end()-1;
  61. for (;it != upper.begin();--it)
  62. if (it == upper.begin() || clockwise(*(it-1),*it,*p_it))
  63. break;
  64. upper.erase(it+1,upper.end());
  65. upper.push_back(*p_it);
  66. }
  67.  
  68. upper.pop_back();
  69. reverse(upper.begin(),upper.end());
  70. upper.pop_back();
  71.  
  72. for (int i = 0; i < upper.size(); ++i)
  73. lower.push_back(upper[i]);
  74.  
  75. return lower;
  76. }
  77.  
  78. int main(){
  79. int N;
  80. //point np = add(make_pair(1,1), normpoint(make_pair(0,0),make_pair(1,0)));
  81. //cout << np.first << " " << np.second << "\n";
  82. //return 0;
  83. while (cin >> N) {
  84. vector<point> points;
  85. int x,y;
  86. for (int i = 0; i < N; ++i) {
  87. cin >> x >> y;
  88. points.push_back(make_pair(x,y));
  89. }
  90. vector<point> conv_hull = convex_hull(points);
  91. int ri,ui,li;
  92. ui = 2;
  93. li = 0;
  94. ri = 1;
  95. double mcir = 14e9;
  96. for (int i = 0; i < conv_hull.size(); i++) {
  97. point a = conv_hull[i];
  98. point b = conv_hull[(i+1)%conv_hull.size()];
  99.  
  100. double maxd = -14e9;
  101. for (int j = (ui)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) {
  102. if (!EQ(distance(a,b,conv_hull[j]),maxd) && distance(a, b, conv_hull[j]) < maxd)
  103. break;
  104. maxd = distance(a,b,conv_hull[j]);
  105. ui = j;
  106. }
  107.  
  108. point np = normpoint(a,b);
  109. maxd = 14e9;
  110. for (int j = (ri)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) {
  111. if (!EQ(distance(b,add(b,np),conv_hull[j]),maxd) && distance(b, add(b,np), conv_hull[j]) > maxd)
  112. break;
  113. maxd = distance(b, add(b,np),conv_hull[j]);
  114. ri = j;
  115. }
  116. maxd = -14e9;
  117. if (i == 0) li = ui;
  118. for (int j = (li)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) {
  119. if (!EQ(distance(b,add(b,np),conv_hull[j]),maxd) && distance(b, add(b,np), conv_hull[j]) < maxd)
  120. break;
  121. maxd = distance(b, add(b,np),conv_hull[j]);
  122. li = j;
  123. }
  124. double cir = 2*abs(distance(a,b,conv_hull[ui])) + 2*(abs(distance(b,add(b,np),conv_hull[li])) + abs(distance(b,add(b,np),conv_hull[ri])));
  125. mcir = min(mcir, cir);
  126. }
  127. cout << mcir << "\n";
  128. }
  129. return 0;
  130. }
  131.  
  132.  
  133.  

Diff to submission s993

fo.cpp

--- c5.s993.cteam026.fo.cpp.0.fo.cpp
+++ c5.s1061.cteam026.fo.cpp.0.fo.cpp
@@ -37,4 +37,10 @@
 }
 
+bool EQ(double a, double b)
+{
+        if (abs(a-b) < 10e-6) return true;
+        return false;
+}
+
 vector<point> convex_hull(vector<point> &Ps) {
         sort(Ps.begin(),Ps.end());
@@ -94,5 +100,5 @@
                         double maxd = -14e9;
                         for (int j = (ui)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) {
-                                if (distance(a, b, conv_hull[j]) < maxd)
+                                if (!EQ(distance(a,b,conv_hull[j]),maxd) && distance(a, b, conv_hull[j]) < maxd)
                                         break;
                                 maxd = distance(a,b,conv_hull[j]);
@@ -103,5 +109,5 @@
                         maxd = 14e9;
                         for (int j = (ri)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) {
-                                if (distance(b, add(b,np), conv_hull[j]) > maxd)
+                                if (!EQ(distance(b,add(b,np),conv_hull[j]),maxd) && distance(b, add(b,np), conv_hull[j]) > maxd)
                                         break;
                                 maxd = distance(b, add(b,np),conv_hull[j]);
@@ -109,7 +115,7 @@
                         }
                         maxd = -14e9;
-                        if (i == 0) li = ri;
+                        if (i == 0) li = ui;
                         for (int j = (li)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) {
-                                if (distance(b, add(b,np), conv_hull[j]) < maxd)
+                                if (!EQ(distance(b,add(b,np),conv_hull[j]),maxd) && distance(b, add(b,np), conv_hull[j]) < maxd)
                                         break;
                                 maxd = distance(b, add(b,np),conv_hull[j]);