Source code for submission s619

fo.cpp

  1. #include <algorithm>
  2. #include <cctype>
  3. #include <cmath>
  4. #include <complex>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18. using namespace std;
  19.  
  20. #define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
  21. #define REP(i,a) for (int i = 0; i < (a); ++i)
  22. #define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
  23. #define FORD(i,a,b) for (int i = (a); i >= (b); --i)
  24. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  25.  
  26. const int INF = 1<<29;
  27. typedef long long ll;
  28. ///////////////////////////////////////////////////////////////////////////
  29.  
  30. struct Vector
  31. {
  32.   double x, y;
  33.  
  34.   Vector(double _x=0.0, double _y=0.0): x(_x), y(_y) {}
  35.  
  36.   bool operator<(const Vector & v) const { return x < v.x || (x == v.x && y < v.y); }
  37.   Vector operator-(const Vector & v) const { return Vector(x-v.x, y-v.y); }
  38.   void operator/=(double n) { x /= n; y/=n; }
  39.  
  40.   double size() const { return sqrt(x*x+y*y); }
  41. };
  42.  
  43. double dot(const Vector & v1, const Vector & v2)
  44. {
  45.   return v1.x * v2.x + v1.y * v2.y;
  46. }
  47.  
  48. double cross(const Vector & v1, const Vector & v2)
  49. {
  50.   return v1.x * v2.y - v1.y * v2.x;
  51. }
  52.  
  53. double direction(const Vector & v1, const Vector & v2, const Vector & point)
  54. {
  55.   return cross(point-v1, v2-v1);
  56. }
  57.  
  58. void convex_hull(vector<Vector> & points, vector<Vector> & hull)
  59. {
  60.   sort(points.begin(), points.end());
  61.   vector<Vector> top, bot;
  62.   REP(i, points.size())
  63.   {
  64.     while (top.size() >= 2 && direction(top[top.size()-2], points[i], top[top.size()-1]) <= 0)
  65.       top.pop_back();
  66.     top.push_back(points[i]);
  67.     while (bot.size() >= 2 && direction(bot[bot.size()-2], points[i], bot[bot.size()-1]) >= 0)
  68.       bot.pop_back();
  69.     bot.push_back(points[i]);
  70.   }
  71.   reverse(bot.begin(), bot.end());
  72.   hull = top;
  73.   if (bot.size() > 2)
  74.     hull.insert(hull.end(), bot.begin()+1, bot.end()-1);
  75. }
  76.  
  77. const int MAX = 10007;
  78.  
  79. int main()
  80. {
  81.   int N;
  82.   while (scanf("%d", &N) == 1)
  83.   {
  84.    vector<Vector> points(N), hull;
  85.    REP(i, N) scanf("%lf%lf", &points[i].x, &points[i].y);
  86.    convex_hull(points, hull);
  87.  
  88.    double res = 1e12;
  89.  
  90.    REP(i, hull.size())
  91.    {
  92.      Vector v = hull[(i+1)%hull.size()] - hull[i];
  93.      v /= v.size();
  94.  
  95.      double x1 = 0.0, x2 = 0.0, y = 0.0;
  96.      REP(j, hull.size())
  97.      {
  98.        Vector v2 = hull[j]-hull[i];
  99.        double d = dot(v, v2);
  100.        x1 = min(x1, d);
  101.        x2 = max(x2, d);
  102.        double d2 = fabs(cross(v, v2));
  103.        y = max(y, d2);
  104.      }
  105.      res = min(res, 2 * (y + (x2-x1)));
  106.    }
  107.  
  108.    printf("%.9lf\n", res);
  109.   }
  110.  
  111.  
  112.   return 0;
  113. }