题目描述:和上题一样,朴素凸包
代码如下
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define size 1000
struct pint
{
int x,
y;
}x[size];
bool cmp(pint p1, pint p2)
{
int temp =
(p1.x - x[0].x) * (p2.y - x[0].y) - (p2.x - x[0].x) * (p1.y -
x[0].y);
if (temp ==
0) return (p1.x >= min(x[0].x, p2.x)
&& p1.x <=
max(x[0].x, p2.x));
else return
temp > 0;
}
bool CrossLeft(pint p1, pint p2, pint p3)//是否严格左转,共线不算左转
{
return
((p3.x - p1.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p3.y - p1.y))
< 0;
}
int ans[size], cnt, n, l;
void Graham()
{
sort(x + 1,
x + n, cmp);cnt = 0;
ans[cnt++] =
0;ans[cnt++] = 1;
for(int i =
2; i < n; i++)
{
while(cnt > 1 &&
!CrossLeft(x[ans[cnt - 2]], x[ans[cnt - 1]], x[i])) cnt--;
ans[cnt++] = i;
}
ans[cnt++] =
0;
}
int tx, ty, tid;
int main()
{
scanf("%d%d", &n, &l);
tx = ty =
1000000;
for(int i =
0; i < n; i++)
{
scanf("%d%d", &x[i].x,
&x[i].y);
if (x[i].y < ty || x[i].y == ty
&& x[i].x <
tx)
{
tx = x[i].x, ty = x[i].y;
tid = i;
}
}
pint temp =
x[tid];x[tid] = x[0];x[0] = temp;
Graham();
double re =
4 * acos(0.0) * l;
for(int i =
0; i < cnt - 1; i++)
re += sqrt((x[ans[i]].x - x[ans[i + 1]].x) * (x[ans[i]].x - x[ans[i
+ 1]].x) + (x[ans[i]].y - x[ans[i + 1]].y) * (x[ans[i]].y - x[ans[i
+ 1]].y) * 1.0);
printf("%.0f\n", re);
return
0;
}
加载中,请稍候......