大家好，又见面了，我是全栈君。
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 29183 | Accepted: 9768 |
Description
Your task is to help poor Architect to save his head, by writing a program that will find the minimum possible length of the wall that he could build around the castle to satisfy King’s requirements.
The task is somewhat simplified by the fact, that the King’s castle has a polygonal shape and is situated on a flat ground. The Architect has already established a Cartesian coordinate system and has precisely measured the coordinates of all castle’s vertices in feet.
Input
Next N lines describe coordinates of castle’s vertices in a clockwise order. Each line contains two integer numbers Xi and Yi separated by a space (-10000 <= Xi, Yi <= 10000) that represent the coordinates of ith vertex. All vertices are different and the sides of the castle do not intersect anywhere except for vertices.
Output
Sample Input
9 100 200 400 300 400 300 300 400 300 400 400 500 400 500 200 350 200 200 200
Sample Output
1628
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct node
{
double x,y;
}a[1005],b[1005];
double cmp(node n,node m)
{
if(n.x != m.x)
return n.x < m.x;
else
return n.y < m.y;
}
double Cross(node a,node b,node c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double dis(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int CH(node* a,int n,node* b)
{
sort(a,a+n,cmp);
int m=0,i;
for(i=0;i<n;i++)
{
while(m > 1 && Cross(b[m-2],b[m-1],a[i]) < 0)
m--;
b[m++]=a[i];
}
int k=m;
for(i=n-2;i>=0;i--)
{
while(m > k && Cross(b[m-2],b[m-1],a[i]) < 0)
m--;
b[m++]=a[i];
}
if(n >1) m--;
return m;
}
int main()
{
int n,m;
while(cin>>n>>m)
{
if(n==0) break;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
int i,j;
for(i=0;i<n;i++)
{
cin>>a[i].x>>a[i].y;
}
int k=CH(a,n,b);
double s=0;
for(i=1;i<k;i++)
s+=dis(b[i-1],b[i]);
s+=dis(b[0],b[k-1])+3.1415927*m*2;
printf("%.0lf\n",s);
}
return 0;
}
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/115553.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
