[poj 1113]Wall[凸包]
1735 ワード
タイトル:
多角形の城の最も短い塀を囲んで、塀は満たす必要があります:城の上のすべての点から少なくとも距離はLです
考え方:
凸包を求め、辺長に半径Lの円の周長を加える.曲がり角からの最短壁は円弧状であるからである.
テストバンプテンプレートに相当します~
多角形の城の最も短い塀を囲んで、塀は満たす必要があります:城の上のすべての点から少なくとも距離はLです
考え方:
凸包を求め、辺長に半径Lの円の周長を加える.曲がり角からの最短壁は円弧状であるからである.
テストバンプテンプレートに相当します~
#include <cstdio>
#include <cmath>
#include <algorithm>
#define PI acos(-1.0)//
using namespace std;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double L = 0.618 - 0.1;
const double R = 0.618 + 0.1;
const int MAXN = 10005;
struct point
{
double x,y;
}res[MAXN],p[MAXN];
int top,n,radius;
/*cross product*/
double cross(point a, point b, point o)//OA X OB
{
return (a.x - o.x)*(b.y - o.y) - (b.x - o.x)*(a.y - o.y);
}
/*square sum*/
double sqsm(point a, point b)
{
return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
bool cmp(point a, point b)
{
if(a.x - b.x > EPS || b.x - a.x > EPS) return a.x < b.x;
return a.y < b.y;
}
void Graham()
{
sort(p, p+n, cmp);
res[0] = p[0];
res[1] = p[1];
top = 1;
for(int i=2;i<n;i++)
{
while(top && cross(p[i], res[top-1], res[top])<=EPS)
top--;
res[++top] = p[i];
}
int mark = top;
res[++top] = p[n-2];
for(int i=n-3;i>=0;i--)
{
while(top>mark && cross(p[i], res[top-1], res[top])<=EPS)
top--;
res[++top] = p[i];
}
}
int main()
{
while(scanf("%d %d",&n,&radius)==2)
{
for(int i=0;i<n;i++)
scanf("%lf %lf",&p[i].x,&p[i].y);
Graham();
double ans = 0;
for(int i=0;i<top;i++)
{
ans += sqrt(sqsm(res[i],res[i+1]));
}
ans += 2* PI* radius;
printf("%.0lf
",ans);
}
}