题意:给定 n 个点,让你用最长的周长把它们严格包围起来,边长只能用小格子边长或者是小格子对角线。
析:先把每个点的上下左右都放到一个集合中,然后求出一个凸包,然后先边长转成题目的方式,也好转两个点的最小的*根号2加上两者差*1.
代码如下:
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <stack>
using namespace std ; typedef long long LL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-10;
const int maxn = 4e5 + 5;
const int mod = 1e9 + 7;
const double sqrt2 = sqrt(2.0);
const char *mark = "+-*";
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
int n, m;
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
} inline double add(double a, double b){
if(abs(a+b) < eps * (abs(a) + abs(b))) return 0;
return a + b;
}
struct Point{
double x, y;
Point(){ }
Point(double xx, double yy) : x(xx), y(yy) { }
Point operator + (Point p){
return Point(add(x, p.x), add(y, p.y));
}
Point operator - (Point p){
return Point(add(x, -p.x), add(y, -p.y));
}
double dot(Point p){
return add(x*p.x, -y*p.y);
}
double det(Point p){
return add(x*p.y, -y*p.x);
}
}; bool cmp(const Point &lhs, const Point &rhs){
if(lhs.x != rhs.x) return lhs.x < rhs.x;
return lhs.y < rhs.y;
} vector<Point> convex_hull(Point *ps, int n){
sort(ps, ps+n, cmp);
int k = 0;
vector<Point> 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;
} double dist(Point p, Point q){
return (p-q).dot(p-q);
} Point ps[maxn]; double solve(int n){
vector<Point> qs = convex_hull(ps, n);
double ans = 0;
int m = qs.size();
for(int i = 0; i < m; ++i){
int x = abs(qs[i].x - qs[(i+1)%m].x);
int y = abs(qs[i].y - qs[(i+1)%m].y);
ans += abs(x-y);
ans += 1.0*min(x, y) * sqrt2;
}
return ans;
} int main(){
while(scanf("%d", &n) == 1){
int cnt = 0;
for(int i = 0; i < n; ++i){
double x, y;
scanf("%lf %lf", &x, &y);
ps[cnt++] = Point(x+1, y);
ps[cnt++] = Point(x, y+1);
ps[cnt++] = Point(x, y-1);
ps[cnt++] = Point(x-1, y);
}
printf("%.6f\n", solve(cnt));
}
return 0;
}