【凸包Graham_Scan算法】HDU 1348 Wall
典型凸包题，求外围城墙的周长
C++代码
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
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;
}
补充：软件开发 , C语言 ,
