牛客假日团队赛5J 护城河 bzoj 1670: [Usaco2006 Oct]Building the Moat护城河的挖掘（凸包的周长）

链接：https://ac.nowcoder.com/acm/contest/984/J

来源：牛客网

护城河

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32768K，其他语言65536K

64bit IO Format: %lld

题目描述

为了防止口渴的食蚁兽进入他的农场，Farmer John决定在他的农场周围挖一条护城河。农场里一共有N(8<=N<=5,000)股泉水，并且，护城河总是笔直地连接在河道上的相邻的两股泉水。护城河必须能保护所有的泉水，也就是说，能包围所有的泉水。泉水一定在护城河的内部，或者恰好在河道上。当然，护城河构成一个封闭的环。

挖护城河是一项昂贵的工程，于是，节约的FJ希望护城河的总长度尽量小。请你写个程序计算一下，在满足需求的条件下，护城河的总长最小是多少。

所有泉水的坐标都在范围为(1..10,000,000,1..10,000,000)的整点上，一股泉水对应着一个唯一确定的坐标。并且，任意三股泉水都不在一条直线上。

以下是一幅包含20股泉水的地图，泉水用""表示：

...-----------------......

../.......................

./.........................

.........................

|........................

|.........................

|..........................

..........................|

.*........................|

.........................|

........................|

.........................

......................./.

......................../..

.......----------------...

（请复制到记事本中用等宽字体查看）

图中的直线，为护城河的最优挖掘方案，即能围住所有泉水的最短路线。

路线从左上角起，经过泉水的坐标依次是：(18,0),(6,-6),(0,-5),(-3,-3),(-17,0),(-7,7),(0,4),(3,3)。绕行一周的路径总长为70.8700576850888(...)。答案只需要保留两位小数，于是输出是70.87。

输入描述:

第1行: 一个整数，N

第2..N+1行: 每行包含2个用空格隔开的整数，x[i]和y[i]，即第i股泉水的位置坐标

输出描述:

第1行: 输出一个数字，表示满足条件的护城河的最短长度。保留两位小数

示例1

输入

复制

20

2 10

3 7

22 15

12 11

20 3

28 9

1 12

9 3

14 14

25 6

8 1

25 1

28 4

24 12

4 15

13 5

26 5

21 11

24 4

1 8

输出

复制

70.87

思路：

模板题，直接看代码吧。

细节见代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define rt return

#define dll(x) scanf("%I64d",&x)

#define xll(x) printf("%I64d\n",x)

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}

ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}

inline void getInt(int* p);

const int maxn = 1000010;

const int inf = 0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

const int MAX=5005;// 最大点数

const int INF=0x3f3f3f3f;//坐标的最大值

// 本模板读入默认是1-n读入

int n;

int top;

struct Node

{

       int x,y;

}p[MAX],S[MAX];//p储存节点的位置，S是凸包的栈

inline bool cmp(Node a,Node b)//比较函数，对点的极角进行排序

{

       double A=atan2((a.y-p[1].y),(a.x-p[1].x));

       double B=atan2((b.y-p[1].y),(b.x-p[1].x));

       if(A!=B)return A<B;

       else    return a.x<b.x; //这里注意一下，如果极角相同，优先放x坐标更小的点

}

long long Cross(Node a,Node b,Node c)//计算叉积

{

       return 1LL*(b.x-a.x)*(c.y-a.y)-1LL*(b.y-a.y)*(c.x-a.x);

}

void Get()//求出凸包

{

       p[0]=(Node){INF,INF};int k;

       for(int i=1;i<=n;++i)//找到最靠近左下的点

              if(p[0].y>p[i].y||(p[0].y==p[i].y&&p[i].x<p[0].x))

               {p[0]=p[i];k=i;}

       swap(p[k],p[1]);

       sort(&p[2],&p[n+1],cmp);//对于剩余点按照极角进行排序

       S[0]=p[1],S[1]=p[2];top=1;//提前在栈中放入节点

       for(int i=3;i<=n;)//枚举其他节点

       {

              if(top&&Cross(S[top-1],p[i],S[top])>=0)

                        top--;//如果当前栈顶不是凸包上的节点则弹出

              else  S[++top]=p[i++];//加入凸包的栈中

       }

       //底下这个玩意用来输出凸包上点的坐标

       //for(int i=0;i<=top;++i)

       //    printf("(%d,%d)\n",S[i].x,S[i].y);

}

double  getdis(Node one ,Node two)

{

    double res=sqrt((one.x-two.x)*(one.x-two.x)+(two.y-one.y)*(two.y-one.y));

    return res;

}

double solve()// 返回凸包的边长 ___注意n=1,n=2时候的特判

{

    double ans=0.00000000000000;

    ans=ans+getdis(S[0],S[top]);

    repd(i,1,top)

    {

        ans=ans+getdis(S[i],S[i-1]);

    }

    return ans;

}

int main()

{

    //freopen("D:\\code\\text\\input.txt","r",stdin);

    //freopen("D:\\code\\text\\output.txt","w",stdout);

    gbtb;

    cin>>n;

    repd(i,1,n)

    {

        cin>>p[i].x>>p[i].y;

    }

    Get();

    cout<<fixed<<setprecision(2)<<solve()<<endl;

    return 0;

}

inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    }

    else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '0';

        }

    }

}

巴特西

牛客假日团队赛5J 护城河 bzoj 1670: [Usaco2006 Oct]Building the Moat护城河的挖掘（凸包的周长）

最新文章

热门文章

巴特西

牛客假日团队赛5J 护城河 bzoj 1670: [Usaco2006 Oct]Building the Moat护城河的挖掘 （凸包的周长）

最新文章

热门文章

牛客假日团队赛5J 护城河 bzoj 1670: [Usaco2006 Oct]Building the Moat护城河的挖掘（凸包的周长）