「cogs896」圈奶牛

2014年2月7日4,0340

描述

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

PROGRAM NAME: fc

INPUT FORMAT(file fc.in)

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

OUTPUT FORMAT(file fc.out)

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

SAMPLE INPUT (file fc.in)

4 8

4 12

5 9.3

7 8

SAMPLE OUTPUT (file fc.out)

12.00

12.00

代码，裸的凸包

graham 凸包算法自行百度。。。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,top;
double ans;
struct data{
   double x,y;
}p[10001],s[10001];
double dis(data a,data b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
double mul(data p1,data p2,data p0)
{return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}
inline bool cmp(data a,data b)
{
	if(mul(a,b,p[0])==0)return dis(a,p[0])<dis(b,p[0]);
	return mul(a,b,p[0])>0;
}
void graham()
{
	top=2;data t;
	int k=0;
	for(int i=1;i<n;i++)
	    if((p[k].y>p[i].y)||(p[k].y==p[i].y&&p[k].x>p[i].x))k=i;
	t=p[0];p[0]=p[k];p[k]=t;
	sort(p+1,p+n,cmp);
	s[0]=p[0],s[1]=p[1],s[2]=p[2];
	for(int i=3;i<n;i++)
	{
		while(top&&mul(p[i],s[top],s[top-1])>=0)
		   top--;
        s[++top]=p[i];
	}
    s[++top]=p[0];
	for(int i=0;i<top;i++)
        ans+=dis(s[i],s[i+1]);
}
int main()
{
    //freopen("fc.in","r",stdin);
	//freopen("fc.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
    graham();
    printf("%.2lf",ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

int n,top;

double ans;

struct data{

double x,y;

}p[10001],s[10001];

double dis(data a,data b)

{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

double mul(data p1,data p2,data p0)

{return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}

inline bool cmp(data a,data b)

{

if(mul(a,b,p[0])==0)return dis(a,p[0])<dis(b,p[0]);

return mul(a,b,p[0])>0;

}

void graham()

{

top=2;data t;

int k=0;

for(int i=1;i<n;i++)

if((p[k].y>p[i].y)||(p[k].y==p[i].y&&p[k].x>p[i].x))k=i;

t=p[0];p[0]=p[k];p[k]=t;

sort(p+1,p+n,cmp);

s[0]=p[0],s[1]=p[1],s[2]=p[2];

for(int i=3;i<n;i++)

{

while(top&&mul(p[i],s[top],s[top-1])>=0)

top--;

s[++top]=p[i];

}

s[++top]=p[0];

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

ans+=dis(s[i],s[i+1]);

}

int main()

{

//freopen("fc.in","r",stdin);

//freopen("fc.out","w",stdout);

scanf("%d",&n);

for(int i=0;i<n;i++)

scanf("%lf%lf",&p[i].x,&p[i].y);

graham();

printf("%.2lf",ans);

return 0;

}

「BZOJ1069」[SCOI2007] 最大土地面积 »

hzwer.com _ Home | http://hzwer.com

「cogs896」圈奶牛

PROGRAM NAME: fc

INPUT FORMAT(file fc.in)

OUTPUT FORMAT(file fc.out)

SAMPLE INPUT (file fc.in)

SAMPLE OUTPUT (file fc.out)

分类目录

热门文章

Myfriends

近期评论