典型凸包题，求外围城墙的周长

C++代码

#include

#include

#include

#include

#include

//#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

#define PI 3.14159265

struct point{

double x, y, angel;

}p[1005], ch[1005];

double dist (point a, point b)

{

return sqrt ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));

}

double multi (point a, point b, point c)

{

double x1, y1, x2, y2;

x1 = b.x - a.x;

y1 = b.y - a.y;

x2 = c.x - b.x;

y2 = c.y - b.y;

return x1*y2 - x2*y1;

}

bool cmp (point a, point b)

{

if (a.y == b.y)

return a.x < b.x;

return a.y < b.y;

}

bool cmp2 (point a, point b)

{

if (a.angel == b.angel)

{

if (a.x == b.x)

return a.y > b.y;

return a.x > b.x;

}

return a.angel < b.angel;

}

int main()

{

int n, i, top, t;

double r, len;

scanf ("%d", &t);

while (t--)

{

scanf ("%d%lf", &n, &r);

for (i = 0; i < n; i++)

scanf ("%lf%lf", &p[i].x, &p[i].y);

sort (p, p+n, cmp); //找到左下角的p[0]

//找相对于p[0]的极角，并把除了p[0]以外的点按照极角排序

for (i = 1; i < n; i++)

p[i].angel = atan2 (p[i].y-p[0].y, p[i].x-p[0].x);

sort (p+1, p+n, cmp2);

//Graham_Scan算法

ch[0] = p[0], ch[1] = p[1], ch[2] = p[2];

top = 3;

for (i = 3; i < n; i++)

{

while (top > 2 && multi (ch[top-2], ch[top-1], p[i]) <= 0)

top--;

ch[top++] = p[i];

}

//求周长

len = dist (ch[0], ch[top-1]);

for (i = 1; i < top; i++)

len += dist (ch[i], ch[i-1]);

len += 2 * PI * r; //加上圆弧，刚好为一个圆！

printf ("%.0lf\n", len);

if (t)

printf ("\n");

}

return 0;

}