Source code for submission s960

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. vector<point> convex_hull(vector<point> &Ps) {
  40. sort(Ps.begin(),Ps.end());
  41. if (Ps.size() < 3) return Ps;
  42. vector<point> lower,upper;
  43. lower.push_back(Ps.front());
  44. upper.push_back(Ps.front());
  45.  
  46. for (vp_it p_it = Ps.begin()+1;p_it != Ps.end(); ++p_it) {
  47. vp_it it = lower.end()-1;
  48. for (;it != lower.begin();--it)
  49. if (it == lower.begin() || counterclockwise(*(it-1),*it,*p_it))
  50. break;
  51. lower.erase(it+1,lower.end());
  52. lower.push_back(*p_it);
  53.  
  54. it = upper.end()-1;
  55. for (;it != upper.begin();--it)
  56. if (it == upper.begin() || clockwise(*(it-1),*it,*p_it))
  57. break;
  58. upper.erase(it+1,upper.end());
  59. upper.push_back(*p_it);
  60. }
  61.  
  62. upper.pop_back();
  63. reverse(upper.begin(),upper.end());
  64. upper.pop_back();
  65.  
  66. for (int i = 0; i < upper.size(); ++i)
  67. lower.push_back(upper[i]);
  68.  
  69. return lower;
  70. }
  71.  
  72. int main(){
  73. int N;
  74. //point np = add(make_pair(1,1), normpoint(make_pair(0,0),make_pair(1,0)));
  75. //cout << np.first << " " << np.second << "\n";
  76. //return 0;
  77. while (cin >> N) {
  78. vector<point> points;
  79. int x,y;
  80. for (int i = 0; i < N; ++i) {
  81. cin >> x >> y;
  82. points.push_back(make_pair(x,y));
  83. }
  84. vector<point> conv_hull = convex_hull(points);
  85. int ri,ui,li;
  86. ui = 2;
  87. li = 0;
  88. ri = 1;
  89. double mcir = 14e9;
  90. for (int i = 0; i < conv_hull.size(); i++) {
  91. point a = conv_hull[i];
  92. point b = conv_hull[(i+1)%conv_hull.size()];
  93.  
  94. double maxd = -14e9;
  95. for (int j = (ui)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) {
  96. if (distance(a, b, conv_hull[j]) <= maxd)
  97. break;
  98. maxd = distance(a,b,conv_hull[j]);
  99. ui = j;
  100. }
  101.  
  102. point np = normpoint(a,b);
  103. maxd = -14e9;
  104. for (int j = (li)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) {
  105. if (distance(b, add(b,np), conv_hull[j]) <= maxd)
  106. break;
  107. maxd = distance(b, add(b,np),conv_hull[j]);
  108. li = j;
  109. }
  110. maxd = 14e9;
  111. for (int j = (ri)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) {
  112. if (distance(b, add(b,np), conv_hull[j]) >= maxd)
  113. break;
  114. maxd = distance(b, add(b,np),conv_hull[j]);
  115. ri = j;
  116. }
  117. 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])));
  118. mcir = min(mcir, cir);
  119. }
  120. cout << mcir << "\n";
  121. }
  122. return 0;
  123. }
  124.  
  125.  
  126.