第一次做凸包,这道题要特殊考虑下,n=2时的情况,要除以二才行。
我是从最左边的点出发,每次取斜率最大的点,一直到最右边的点。
然后从最左边的点出发,每次取斜率最低的点,一直到最右边的点。
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
const double eps=1e-9;
struct node
{
double x,y;
}f[105];
bool flag[105];
int n;
bool cmp(node a,node b)
{
return fabs(a.x-b.x)<eps?(a.y<b.y):(a.x<b.x);
}
double xielv(int a,int b)//求斜率
{
return (f[a].y-f[b].y)/(f[a].x-f[b].x);
}
double dis(int a,int b)//求距离
{
double xx=f[a].x-f[b].x,yy=f[a].y-f[b].y;
return sqrt(xx*xx+yy*yy);
}
void calans()//计算最短周长
{
int i,j,now=0,maxi;
double ans=0;
while(1)
{
double max=-4000000;//斜率最大值
maxi=now;
for(i=1;i<n;i++)
{
if(flag[i])continue;
if(-f[i].x+f[now].x>eps)continue;//在当前点的左边,不考虑
if(fabs(f[now].x-f[i].x)<eps)
{
if(f[now].y>f[i].y)//在当前点的正下方,不考虑
continue;
maxi=i;
break;
}
else
{
double p=xielv(now,i);
if(p>max)
{
maxi=i;
max=p;
}
}
}
flag[maxi]=1;
ans+=dis(now,maxi);
if(maxi==now)
{
flag[maxi]=0;//最后右边的点要计算两次,去除标记
break;
}
now=maxi;
}
now=0;
while(1)//每次取斜率最小的点
{
double min=4000000;
int mini=now;
for(i=1;i<n;i++)
{
if(flag[i])continue;
if(-f[i].x+f[now].x>eps)continue;//在当前点的左边,不考虑
if(fabs(f[i].x-f[now].x)<eps)
{
if(f[i].x+0.1<f[n-1].x)//在当前点的正下方,不考虑
continue;
mini=i;
break;
}
double p=xielv(now,i);
if(p<min)
{
mini=i;
min=p;
}
}
ans+=dis(now,mini);
flag[mini]=1;
if(mini==now)
break;
now=mini;
}
if(n==2)ans/=2;//n=2时,除以二
printf("%.2f\n",ans);
}
int main()
{
int i,j;
while(scanf("%d",&n)!=-1&&n)
{
memset(flag,0,sizeof(flag));
for(i=0;i<n;i++)
scanf("%lf%lf",&f[i].x,&f[i].y);
sort(f,f+n,cmp);
calans();
}
return 0;
}
分享到:
相关推荐
凸包经典入门,求凸包周长.00000000000000000000000
For a positive integer n, let’s denote function f(n,m) as the m-th smallest integer x that x>n and gcd(x,n)=1. For example, f(5,1)=6 and f(5,5)=11. You are given the value of m and (f(n,m)?n)⊕n,...
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input...
3.the number of rooted, trivalent trees with n+1 nodes; (hdu 1131) 4.the number of paths of length 2n through an n-by-n grid that do not rise above the main diagonal. 在这里记下一个重要的结论,一个...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
此程序为hdu的acm2010题,就是解决水仙花数问题
杭电hdu acm资料所用杭电的acm题
包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...
HDU一部分题目原码,大部分是可运行的,可能有几题不完整
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
hdu 1005.比较简单的一道题,有兴趣的可以看看。
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
100道 acm C语言 hdu 解题报告
ACM hdu 代码大全3000例,hdu已经AC的3000例代码,部分代码有详细解析
HDU1059的代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门