# Craters

General Warren Pierce has a bit of a problem. He’s in charge of a new type of drone-delivered explosive and they’ve been testing it out in the Nevada desert, far enough from any population center to avoid civilian casualties and prying eyes. Unfortunately word has gotten out about these experiments and now there’s the possibility of careless on-lookers, nefarious spies, or even worse — nosy reporters! To keep them away from the testing area, Warren wants to erect a single fence surrounding all of the circular craters produced by the explosions. However, due to various funding cuts (to support tax cuts for the you-know-who) he can’t just put up miles and miles of fencing like in the good old days. He figures that if he can keep people at least 10 yards away from any crater he’ll be okay, but he’s unsure of how much fencing to request. Given the locations and sizes of the craters, can you help the General determine the minimum amount of fencing he needs? An example with three craters (specified in Sample Input 1) is shown below.

Display the minimum amount of fencing (in yards) needed to cordon off the craters, with an absolute or relative error of at most 10−6.

# Input

The first line of input contains a single positive integer n (n $≤$200), the number of craters. After this are n lines specifying the location and radius of each crater. Each of these lines contains 3 integers x y r, where x and y specify the location of a crater (|x,y| ≤ 10000) and r is its radius (0 < r $≤$5000). All units are in yards.

Second line contains n integers fi — lengths of filenames. i-th of those integers represents length of i-th filename in the lexicographically ordered list (1 ≤ fi ≤ w).

# Output

Print one integer — number of lines l, printed by "dir -C" command.

# Examples

input

3
0 0 100
-60 200 40
350 50 150

output

1715.91229929

# Solution

# 思路

第一反应是信用卡凸包。。但是马上就发现了因为圆角的半径不同不能这样。 看到圆的数量这么小就开始动了歪脑筋……把圆割成若干个点开始跑凸包。

# Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>
#include <ctime>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
#include <deque>
using namespace std;
const double pi = acos(-1.0);
int n, top;
const int N = 2e6 + 10;
struct P
{
    double x, y;
} p[N], s[N];
double dis(P a, P b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
P operator - (P a, P b)
{
    P t;
    t.x = a.x - b.x;
    t.y = a.y - b.y;
    return t;
}
double operator*(P a, P b)
{
    return a.x * b.y - a.y * b.x;
}
bool operator < (P a, P b)
{
    double t = (a - p[1]) * (b - p[1]);
    if (t == 0)
        return dis(a, p[1]) < dis(b, p[1]);
    return t < 0;
}
double cross_product(P a, P b, P c)
{
    return (b - a) * (c - a);
}
void graham()
{
    int k = 1;
    for (int i = 2; i <= n; i++)
        if (p[k].y > p[i].y || (p[k].y == p[i].y && p[k].x > p[i].x))
            k = i;
    swap(p[1], p[k]);
    sort(p + 2, p + n + 1);
    s[++top] = p[1];
    s[++top] = p[2];
    for (int i = 3; i <= n; i++)
    {
        while (top > 1 && (p[i] - s[top - 1]) * (s[top] - s[top - 1]) <= 0)
            top--;
        s[++top] = p[i];
    }
}
double cal()
{
    double ans = dis(s[top], s[1]);
    for (int i = 1; i < top; ++i)
        ans += dis(s[i], s[i + 1]);
    return ans;
}
int main()
{
    int cnt = 0; double x, y, r;
    scanf("%d", &cnt);
    n = 0;
    for (int i = 1; i <= cnt; ++i)
    {
        scanf("%lf%lf%lf", &x, &y, &r);
        r += 10;
        for (int j = 0; j < 5000; ++j)
        {
            double theta = 2 * pi * ((double)j / 5000);
            p[++n] = (P){x + r * cos(theta), y + r * sin(theta)};
        }
    }
    graham();
    printf("%.6lf", cal());
    return 0;
}