Convex Hull Algorithm
The Convex Hull Algorithm refers to a group of computational geometry algorithms that generate the smallest convex polygon that contains all the points of a given set in a two-dimensional plane. The convex hull is akin to stretching a rubber band around the set of points, such that it outlines the outermost points, forming a convex shape. The algorithms used to find the convex hull may vary, but some well-known approaches include the Gift Wrapping Algorithm (Jarvis March), Graham's Scan, QuickHull, and Chan's Algorithm. These algorithms have diverse applications, including computer graphics, pattern recognition, image processing, and spatial data analysis.
The efficiency of each algorithm can differ depending on the specific problem and input size. Gift Wrapping Algorithm has a time complexity of O(nh), where n is the number of input points and h is the number of convex hull vertices. Graham's Scan has a time complexity of O(n log n) and is generally faster in practice. QuickHull, inspired by the QuickSort algorithm, has an average-case complexity of O(n log n) but can degrade to O(n^2) in the worst case. Chan's Algorithm, a hybrid of the previous two approaches, has the optimal time complexity of O(n log h). The algorithm choice depends on the problem's constraints and the desired trade-offs between computational speed and implementation complexity.
/**********************************************************************************
Convex Hull [ Graham-Andrew method, O(NlogN) ]
Based on problem 638 from informatics.mccme.ru:
http://informatics.mccme.ru/mod/statements/view3.php?chapterid=638
Tested on problem 290 from informatics.mccme.ru:
http://informatics.mccme.ru/mod/statements/view3.php?id=&chapterid=290
**********************************************************************************/
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define sqr(x) ((x) * (x))
const double pi = acos(-1.0);
struct point {
double x, y;
};
int n;
vector <point> p, hull;
double ans;
bool cmp(point a, point b) {
return (a.x < b.x || (a.x == b.x && a.y < b.y));
}
bool eq(point a, point b) {
return (a.x == b.x && a.y == b.y);
}
bool isCCW(point a, point b, point c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
}
void setConvexHull(vector <point> p, vector <point> &h) {
sort(p.begin(), p.end(), cmp);
p.erase(unique(p.begin(), p.end(), eq), p.end());
vector <point> up, down;
point head = p[0], tail = p.back();
up.push_back(head); down.push_back(head);
for (int i = 1; i < (int) p.size(); i++) {
if (i == (int) p.size() - 1 || !isCCW(tail, head, p[i])) {
while ( (int) up.size() >= 2 && isCCW(up[up.size() - 2], up.back(), p[i]) )
up.pop_back();
up.push_back(p[i]);
}
if (i == (int) p.size() - 1 || isCCW(tail, head, p[i])) {
while ( (int) down.size() >= 2 && !isCCW(down[down.size() - 2], down.back(), p[i]) )
down.pop_back();
down.push_back(p[i]);
}
}
h.clear();
for (int i = 0; i < (int) up.size(); i++)
h.push_back(up[i]);
for (int i = (int) down.size() - 2; i > 0; i--)
h.push_back(down[i]);
}
double dist(point a, point b) {
return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}
double getPerimeter(vector <point> p) {
double per = 0;
for (int i = 1; i < (int) p.size(); i++)
per += dist(p[i - 1], p[i]);
per += dist(p.back(), p[0]);
return per;
}
int main() {
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
point tmp;
scanf("%lf %lf", &tmp.x, &tmp.y);
p.push_back(tmp);
}
setConvexHull(p, hull);
ans = getPerimeter(hull);
printf("%.1lf", ans);
return 0;
}
