作者在 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;
}
#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;
}