HDU 1348 Wall
就是求出凸包,计算凸包周长,然后加上圆周长即可
代码:
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int MAXN=1000; struct Point { int x, y; } list[MAXN]; int stack[MAXN], top; int xmult(Point p0, Point p1, Point p2) { return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x); } double dist(Point p1,Point p2) { return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y)); } //极角排序函数 , 角度相同则距离小的在前面 bool cmp(Point p1,Point p2) { int tmp= xmult(list[0], p1, p2); if(tmp > 0) return true; else if(tmp == 0 && dist(list[0], p1) < dist(list[0], p2)) return true; else return false; } //输入并把最左下方的点放在list[0]并且进行极角排序 void init(int n) { int i, k; Point p0; scanf("%d%d", &list[0].x, &list[0].y); p0.x = list[0].x; p0.y = list[0].y; k = 0; for(i = 1; i < n; i++) { scanf("%d%d", &list[i].x, &list[i].y); if((p0.y > list[i].y) || ((p0.y == list[i].y) && (p0.x > list[i].x))) { p0.x = list[i].x; p0.y = list[i].y; k = i; } } list[k] = list[0]; list[0] = p0; sort(list + 1, list + n, cmp); } void graham(int n) { int i; if(n == 1) {top = 0; stack[0] = 0;} if(n == 2) { top = 1; stack[0] = 0; stack[1] = 1; } if(n > 2) { for(i = 0; i <= 1; i++) stack[i] = i; top = 1; for(i = 2; i < n; i++) { while(top > 0 && xmult(list[stack[top - 1]], list[stack[top]], list[i]) <= 0) top--; top++; stack[top]=i; } } } const double pi = acos(-1.0); int t, n, r; int main() { scanf("%d", &t); while (t--) { scanf("%d%d", &n, &r); init(n); graham(n); double ans = 2 * pi * r; for (int i = 0; i < top; i++) ans += dist(list[stack[i]], list[stack[i + 1]]); ans += dist(list[stack[top]], list[stack[0]]); printf("%.0lf\n", ans); if (t) printf("\n"); } return 0; }