/*------------------------------------------------------------------------------ * problem024.cc: Bear Leash (14.7.1) **----------------------------------------------------------------------------*/ /* Copyright (c) 2009 Peter Bui. All Rights Reserved. * * Peter Bui * **------------------------------------------------------------------------------ * Includes **----------------------------------------------------------------------------*/ #include #include #include #include #include #include #include #include using namespace std; /*------------------------------------------------------------------------------ * Data Structures **----------------------------------------------------------------------------*/ typedef struct { double x; double y; } Point; /*------------------------------------------------------------------------------ * Global Variables **----------------------------------------------------------------------------*/ static Point FirstPoint; /*------------------------------------------------------------------------------ * Functions **----------------------------------------------------------------------------*/ static int read_points(vector &p) { int npoints = 0; if (cin >> npoints) { p = vector(npoints + 1); p[0].x = p[0].y = 0.0; for (int i = 1; i <= npoints; i++) cin >> p[i].x >> p[i].y; } return (npoints); } static void print_points(vector &p) { for (size_t i = 0; i < p.size(); i++) cout << fixed << setprecision(2) << p[i].x << ' ' << p[i].y << endl; } static double compute_distance(const Point &p1, const Point &p2) { double dx = (p2.x - p1.x); double dy = (p2.y - p1.y); return (sqrt((dx * dx) + (dy * dy))); } static bool compare_points_by_yx(const Point &p1, const Point &p2) { if (p1.y < p2.y) return (true); if (p1.y > p2.y) return (false); if (p1.x < p2.x) return (true); if (p1.x > p2.x) return (false); return (false); } static double ccw(const Point &p1, const Point &p2, const Point &p3) { return ((p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x)); } static bool compare_points_by_angle(const Point &p1, const Point &p2) { double result; result = ccw(FirstPoint, p1, p2); if (ccw == 0) return (compute_distance(FirstPoint, p1) < compute_distance(FirstPoint, p2)); else return (result > 0); } static void compute_hull(vector &p) { int h; if (p.size() <= 3) return; stable_sort(p.begin(), p.end(), compare_points_by_yx); FirstPoint = p[0]; stable_sort(p.begin() + 1, p.end(), compare_points_by_angle); h = 1; for (size_t i = 2; i < p.size(); i++) { while (h > 0 && ccw(p[h - 1], p[h], p[i]) < 0.0) h -= 1; h += 1; p[h].x = p[i].x; p[h].y = p[i].y; } p.resize(h + 1); } static void analyze_hull(vector &p) { Point origin = { 0.0, 0.0 }; int pidx; double dmin, dtmp; for (size_t i = 0; i < p.size(); i++) if (ccw(p[i], origin, p[(i + 1) % p.size()]) == 0.0) return; pidx = 0; dmin = INT_MAX; for (size_t i = 0; i < p.size(); i++) { dtmp = compute_distance(p[i], origin) + compute_distance(origin, p[(i + 1) % p.size()]); if (dtmp < dmin) { pidx = i + 1; dmin = dtmp; } } p.insert(p.begin() + pidx, origin); } static double compute_hull_size(vector &p) { double s; s = 0.0; for (size_t i = 0; i < p.size(); i++) s += compute_distance(p[i], p[(i + 1) % p.size()]); return (s); } /*------------------------------------------------------------------------------ * Main Execution **----------------------------------------------------------------------------*/ int main(int argc, char* argv[]) { vector p; while (read_points(p)) { compute_hull(p); analyze_hull(p); cout << fixed << setprecision(2) << compute_hull_size(p) + 2.0 << endl; } return (EXIT_SUCCESS); } /*------------------------------------------------------------------------------ * vim: sts=4 sw=4 ts=8 ft=cpp **----------------------------------------------------------------------------*/