5.1.1 Fencing the Cows 圈奶牛

5.1.1 Fencing the Cows 圈奶牛

时间: 1ms        内存:64M

描述:

农夫约翰想要建造一个围栏用来围住他的奶牛,可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标,计算最短的能够围住这些点的围栏的长度。

输入:

输入数据的第一行包括一个整数 N。N(0 <= N <= 10,000)表示农夫约翰想要围住的放牧点的数目。接下来 N 行,每行由两个实数组成,Xi 和 Yi,对应平面上的放牧点坐标(-1,000,000 <= Xi,Yi <= 1,000,000)。数字用小数表示。

输出:

输出必须包括一个实数,表示必须的围栏的长度。答案保留两位小数。

示例输入:

4
4 8
4 12
5 9.3
7 8

示例输出:

12.00

提示:

参考答案(内存最优[1520]):

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
struct point
{
    double x, y;
};
bool mult(point sp,point ep,point op){
    return (sp.x-op.x)*(ep.y-op.y)>=(ep.x-op.x)*(sp.y-op.y);
}
bool operator < (const point &l,const point &r)
{
    return l.y<r.y||(l.y==r.y&&l.x<r.x);
}
int gra(point pnt[],int n,point res[])
{
    int i,len,top=1;
    sort(pnt,pnt+n);
    if(n==0)return 0;res[0]=pnt[0];
    if(n==1)return 1;res[1]=pnt[1];
    if(n==2)return 2;res[2]=pnt[2];
    for(i=2;i<n;i++){
        while(top&&mult(pnt[i],res[top],res[top-1]))
            top--;
        res[++top]=pnt[i];
    }
    len=top;
    res[++top]=pnt[n-2];
    for(i=n-3;i>=0;i--){
        while(top!=len&&mult(pnt[i],res[top],res[top-1]))
            top--;
        res[++top]=pnt[i];
    }
    return top;
}
double dis(point a,point b)
{
    return sqrt(pow(fabs(a.x-b.x),2)+pow(fabs(a.y-b.y),2));
}
int main()
{
    int n,i;
    double a,b,sumx;
    point p[10001],r[10001];
    while(cin>>n){
        for(i=0;i<n;i++){
            cin>>a>>b;
            p[i].x=a;
            p[i].y=b;
        }
        int x=gra(p,n,r);
        sumx=0;
        for(i=1;i<x;i++){
            sumx+=dis(r[i],r[i-1]);
        }
        sumx+=dis(r[0],r[x-1]);
        printf("%.2lf\n",sumx);
    }
    return 0;
}

参考答案(时间最优[108]):

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
struct point
{
    double x, y;
};
bool mult(point sp,point ep,point op){
    return (sp.x-op.x)*(ep.y-op.y)>=(ep.x-op.x)*(sp.y-op.y);
}
bool operator < (const point &l,const point &r)
{
    return l.y<r.y||(l.y==r.y&&l.x<r.x);
}
int gra(point pnt[],int n,point res[])
{
    int i,len,top=1;
    sort(pnt,pnt+n);
    if(n==0)return 0;res[0]=pnt[0];
    if(n==1)return 1;res[1]=pnt[1];
    if(n==2)return 2;res[2]=pnt[2];
    for(i=2;i<n;i++){
        while(top&&mult(pnt[i],res[top],res[top-1]))
            top--;
        res[++top]=pnt[i];
    }
    len=top;
    res[++top]=pnt[n-2];
    for(i=n-3;i>=0;i--){
        while(top!=len&&mult(pnt[i],res[top],res[top-1]))
            top--;
        res[++top]=pnt[i];
    }
    return top;
}
double dis(point a,point b)
{
    return sqrt(pow(fabs(a.x-b.x),2)+pow(fabs(a.y-b.y),2));
}
int main()
{
    int n,i;
    double a,b,sumx;
    point p[10001],r[10001];
    while(cin>>n){
        for(i=0;i<n;i++){
            cin>>a>>b;
            p[i].x=a;
            p[i].y=b;
        }
        int x=gra(p,n,r);
        sumx=0;
        for(i=1;i<x;i++){
            sumx+=dis(r[i],r[i-1]);
        }
        sumx+=dis(r[0],r[x-1]);
        printf("%.2lf\n",sumx);
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注