本文共 1949 字，大约阅读时间需要 6 分钟。
hdu ：
题意：给你n个数的坐标，用一根绳子把它们围起来，问你需要多长的绳子？
（当数的个数为2时特判 即两点的距离，这是因为一条直线不应再回去围了）
题解：简单的凸包；
code：
#include#include #include #include #include using namespace std;#define eps 1e-6int top , n;//点struct POINT{ double x, y; POINT(){ } POINT(double a, double b){ x = a; y = b; }}p[105],st[105];//线段struct Seg{ POINT a, b; Seg() { } Seg(POINT x, POINT y){ a = x; b = y; }};//叉乘double cross(POINT o, POINT a, POINT b){ return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);}//多边形面积，需要有顺序，顺(逆)时针。double area(){ double ans = 0; for(int i = 1; i < top; i ++){ ans += cross(p[0], p[i], p[i + 1]); } return ans;}//找凸包基点排序bool cmp0(POINT a, POINT b){ if(a.y < b.y) return true; else if(a.y == b.y && a.x < b.x) return true; return false;}double dis(POINT a,POINT b){ return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );}//极角排序bool cmp1(POINT a, POINT b){ if(cross(p[0], a, b) > eps) return true; else if(fabs(cross(p[0], a, b)) < eps && dis(p[0], a) - dis(p[0], b) > eps) return true; return false;}//Graham_scan 求凸包.所求为纯净凸包...void Graham_scan(){ sort(p, p + n, cmp0); sort(p + 1, p + n, cmp1); top = 0; p[n] = p[0]; st[top ++] = p[0]; st[top ++] = p[1]; for(int i = 2; i <= n; i ++){ while(top > 2 && (cross(st[top - 1], st[top - 2], p[i]) > eps || fabs(cross(st[top - 1], st[top - 2], p[i])) < eps)) top --; st[top ++] = p[i]; } top --;}int main(){ while(scanf("%d",&n),n){ for(int i = 0;i < n;i++) scanf("%lf %lf",&p[i].x,&p[i].y); if(n == 2) {printf("%.2lf\n",dis(p[0],p[1]));continue;} Graham_scan(); double sumd = 0; for(int i = 0;i < top;i++) sumd += dis(st[i],st[i+1]); printf("%.2lf\n",sumd); }}
poj :
题意：类似于上题，不过会多加一个圆的周长，因为绳子是绕圆柱的围成多边形后即多了一个圆的周长；
转载地址：http://ocsgi.baihongyu.com/