PCK2016-yo-8.cpp

#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef complex<int> Point;

bool Comp(const Point &p, const Point &q)
{
    if (p.real() != q.real()) return p.real() < q.real();
    return p.imag() < q.imag();
}

int Cross(const Point &p, const Point &q)
{
    return p.real()*q.imag() - p.imag()*q.real();
}

bool IsNG(const Point &p1, const Point &p2, const Point &p3)
{
    return Cross(p2 - p3, p1 - p2) <= 0;
}

double GetDistance(const Point &p, const Point &q)
{
    int dx = p.real() - q.real();
    int dy = p.imag() - q.imag();
    return sqrt(dx*dx + dy*dy);
}

vector<Point> SortReew(vector<Point> ps)
{
    sort(ps.begin(), ps.end(), Comp);
    vector<Point> u;
    for (int i = 0; i < ps.size(); i++)
    {
        while (u.size() > 1 && IsNG(ps[i], u[u.size() - 1], u[u.size() - 2]))
            u.pop_back();
        u.push_back(ps[i]);
    }
    vector<Point> d;
    for (int i = ps.size() - 1; i >= 0; i--)
    {
        while (d.size() > 1 && IsNG(ps[i], d[d.size() - 1], d[d.size() - 2]))
            d.pop_back();
        d.push_back(ps[i]);
    }
    for (int i = 1; i < d.size() - 1; i++)
    {
        u.push_back(d[i]);
    }
    return u;
}

struct UF
{
    vector<int> par;
    UF(int n)
    {
        par.resize(n);
        for (int i = 0; i < n; i++) par[i] = i;
    }
    int Find(int x)
    {
        if (x == par[x]) return x;
        return par[x] = Find(par[x]);
    }
    bool Unite(int a, int b)
    {
        if (Find(a) == Find(b)) return false;
        par[Find(b)] = Find(a);
        return true;
    }
};

int V, R;
map< pair<int, int>, int> m;

struct Edge
{
    int a, b;
    double cost;
    Edge() {}
    Edge(int a, int b, double cost) : a(a), b(b), cost(cost) {}
    bool operator < (const Edge &e) const
    {
        return cost < e.cost;
    }
};

signed main()
{
    cin >> V >> R;
    vector<Point> v(V);
    for (int i = 0; i < V; i++)
    {
        cin >> v[i].real() >> v[i].imag();
        m[make_pair(v[i].real(), v[i].imag())] = i;
    }
    double ans = 0;
    vector<Point> ret = SortReew(v);
    UF uf(V);
    for (int i = 0; i < ret.size(); i++)
    {
        Point p = ret[i];
        Point q = ret[(i+1)%ret.size()];
        int a = m[make_pair(p.real(), p.imag())];
        int b = m[make_pair(q.real(), q.imag())];
        uf.Unite(a,b);
        ans += GetDistance(v[a], v[b]);
        //cout<<"\t"<<a<<" "<<b<<endl;
    }
    //printf("%.20f\n",ans);
    /*for (int i = 0; i < ret.size(); i++)
    {
        printf("%lld %lld\n", ret[i].real(), ret[i].imag());
    }*/
    vector<Edge> es;
    for (int i = 0; i < R; i++)
    {
        int a, b;
        cin >> a >> b; a--; b--;
        es.push_back( Edge(a, b, GetDistance(v[a], v[b]) ));
    }
    sort(es.begin(), es.end());
    for (int i = 0; i < es.size(); i++)
    {
        if (uf.Unite(es[i].a, es[i].b)) ans += es[i].cost;
    }
    printf("%.20f\n", ans);
    return 0;
}