USACO fc構造凸包
4785 ワード
本題の意味は、凸包を構築して凸包の周長を求めることです.コードは次のとおりです.
/*
ID: m1500293
LANG: C++
PROG: fc
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
double eps = 1e-10;
struct P
{
double x, y;
P(double x=0, double y=0):x(x), y(y) {}
double add(double a, double b){
if(abs(a+b)<eps*(abs(a)+abs(b))) return 0;
return a+b;
}
P operator + (P p){
return P(add(x, p.x), add(y, p.y));
}
P operator - (P p){
return P(add(x, -p.x), add(y, -p.y));
}
P operator *(double d){
return P(x*d, y*d);
}
double dot(P p){ //
return add(x*p.x, y*p.y);
}
double det(P p){ //
return add(x*p.y, -y*p.x);
}
}ps[10000 + 100];
double dist(P a, P b)
{
return sqrt((b-a).dot(b-a));
}
bool cmp_x(const P& p, const P& q)
{
if(p.x!=q.x) return p.x < q.x;
return p.y < q.y;
}
vector<P> convex_hull(P *ps, int n)
{
sort(ps, ps+n, cmp_x);
int k = 0; //
vector<P> qs(n*2);
//
for(int i=0; i<n; i++)
{
while(k>1 && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0) k--;
qs[k++] = ps[i];
}
//
for(int i=n-2,t=k; i>=0; i--)
{
while(k>t && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0) k--;
qs[k++] = ps[i];
}
qs.resize(k-1);
return qs;
}
vector<P> hulls;
int main()
{
freopen("fc.in", "r", stdin);
freopen("fc.out", "w", stdout);
int n;
scanf("%d", &n);
for(int i=0; i<n; i++)
{
double x, y;
scanf("%lf%lf", &x, &y);
ps[i] = P(x, y);
}
hulls = convex_hull(ps, n);
double dis = 0;
for(int i=1; i<hulls.size(); i++)
dis += dist(hulls[i], hulls[i-1]);
dis += dist(hulls[hulls.size()-1], hulls[0]);
printf("%.2f
", dis);
return 0;
}