点我看题

咱们先看个图：

看完图以后有没有觉得很显然：

答案就是求个凸包周长加一个圆的周长

#include<bits/stdc++.h> #define maxn 1003 #define db double #define ll long long #define met(a, b) memset(a, b, sizeof(a)) #define pi acos(-1.0) #define _rep(i, a, b) for(int i = (a); i <= (b); i++) #define _rev(i, a, b) for(int i = (a); i >= (b); i--) #define _for(i, a, b) for(int i = (a); i < (b); i++) using namespace std; struct Point { db x, y; Point(db a, db b) : x(a), y(b) {}; Point() {} bool operator < (const Point& a)const { return x == a.x ? y < a.y : x < a.x; } Point operator - (const Point& a) { return Point(x - a.x, y - a.y); } Point operator + (const Point& a) { return Point(x + a.x, y + a.y); } db get_dis(const Point& a) { return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y)); } }pnt[maxn], hull[maxn]; inline db Cross(Point a, Point b) { return a.x * b.y - a.y * b.x; } db out, r; int n; int ConverxHull(Point p[], int n, Point ch[]) { sort(pnt + 1, pnt + 1 + n); int m = 0; _rep(i, 1, n) { while (m > 1 && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m--; ch[m++] = p[i]; } int k = m; _rev(i, n - 1, 1) { while (m > k && Cross(ch[m - 1] - ch[m - 2], p[i] - ch[m - 2]) <= 0) m--; ch[m++] = p[i]; } if (n > 1)m--; return m; } int main() { ios::sync_with_stdio(0); int t; cin >> t; while (t--) { cin >> n >> r; db dis = 0; _rep(i, 1, n) { cin >> pnt[i].x >> pnt[i].y; } int m = ConverxHull(pnt, n, hull); _rep(i, 2, m) { dis += hull[i].get_dis(hull[i - 1]); } dis += hull[1].get_dis(hull[m]); met(hull, 0), met(pnt, 0); dis += 2 * pi * r; dis = (int)(dis + 0.5); cout << (int)dis << endl; if (t != 0)cout << endl; } system("pause"); }