pku1113wall

作者在 2010-08-01 11:37:05 发布以下内容
//3 <= N <= 1000)  1 <= L <= 1000) (-10000 <= Xi, Yi <= 10000)

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const double pi=acos(-1.0);
struct point   //
{   double x,y;  };
double dist(point p1,point p2)  //两点间的距离
{  
    double x1=p1.x-p2.x,y1=p1.y-p2.y;
    return sqrt(x1*x1+y1*y1);  
}
/*==================================================*\
| Graham 求凸包 O(N * logN)
| CALL: nr = graham(pnt, int n, res); res[]为凸包点集;
\*==================================================
*/
bool mult(point sp, point ep, point op){
     return (sp.x - op.x) * (ep.y - op.y)
         >= (ep.x - op.x) * (sp.y - op.y);
}
bool operator < (const point &l, const point &r){
     return l.y < r.y || (l.y == r.y && l.x < r.x);
}
int graham(point pnt[], int n, point res[]){
     int i, len, k = 0, top = 1;
     sort(pnt, pnt + n);
     if (n == 0) return 0; res[0] = pnt[0];
     if (n == 1) return 1; res[1] = pnt[1];
     if (n == 2) return 2; res[2] = pnt[2];
     for (i = 2; i < n; i++) {
         while (top && mult(pnt[i], res[top], res[top-1]))
              top--;
         res[++top] = pnt[i];
     }
     len = top; res[++top] = pnt[n - 2];
     for (i = n - 3; i >= 0; i--) {
         while (top!=len && mult(pnt[i], res[top],res[top-1])) top--;
         res[++top] = pnt[i];
     }                    
     return top;  // 返回凸包中点的个数
}


int main()
{
    int n,len,amount;
    int i,j;
    double d;
    point p[1005],res[1005];
    while(cin>>n>>len)
    {
         for(i=0;i<n;i++)
           cin>>p[i].x>>p[i].y;
         amount=graham(p,n,res);d=0.0;
         for(i=0;i<amount;i++)
           d+=dist(res[i],res[(i+1)%amount]);
         d+=2*pi*len; //注意并不是pi/2*len*amount,容易由长方形产生误解。
         printf("%ld\n",(long)(d+0.5));
    }
    system("pause");
    return 0;
}

计算几何 | 阅读 742 次
文章评论,共0条
游客请输入验证码
最新评论