/*
几何 凸包
顺时针!!!
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
//#include<map>
#include<math.h>
using namespace std;
typedef long long ll;
//typedef __int64 int64;
const int maxn = 105;
const int inf = 0x7fffffff;
const int pi=acos(-1.0);
struct node{
int x,y;
bool operator <( const node &a ) const {
return y<a.y||(y==a.y&&x<a.x);
}
};
node pnt[ maxn ],res[ maxn ];
int cross( node sp,node ep,node op ){
return (sp.x - op.x) * (ep.y - op.y)-(ep.x - op.x) * (sp.y - op.y);
}
/*
ep
|
|
op----sp
( from sp to ep )
*/
double dis( node a,node b ){
double sum=0;
sum=1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y);
return sqrt( sum );
}//两点之间的距离
int graham( int n ){
int top=1;
sort( pnt,pnt+n );
if( n==0 ) return 0;
else res[ 0 ]=pnt[ 0 ];
if( n==1 ) return 1;
else res[ 1 ]=pnt[ 1 ];
if( n==2 ) return 2;
else res[ 2 ]=pnt[ 2 ];
for( int i=2;i<n;i++ ){
while( top&&cross( res[ top-1 ],pnt[ i ],res[ top ] )>=0 )
top--;
res[ ++top ]=pnt[ i ];
}
int len=top;
res[ ++top ]=pnt[ n-2 ];
for( int i=n-3;i>=0;i-- ){
while( top!=len&&cross( res[ top-1 ],pnt[ i ],res[ top ] )>=0 )
top--;
res[ ++top ]=pnt[ i ];
}
return top;//返回res中的点的个数
}
int main(){
int n;
while( scanf("%d",&n)==1,n ){
for( int i=0;i<n;i++ )
scanf("%d%d",&pnt[ i ].x,&pnt[ i ].y);
if( n==1 )
{
printf("0.00\n");
continue;
}
if( n==2 )
{
printf("%.2lf\n",dis( pnt[0],pnt[1] ) );
continue;
}//注意这两个情况的讨论!!!
int cnt=graham( n );
double ans=0;
for( int i=0;i<cnt;i++ ){
if( i==cnt-1 ){
ans+=( dis( res[ cnt-1 ],res[ 0 ] ) );
}
else{
ans+=( dis( res[ i ],res[ i+1 ] ) );
}
}
printf("%.2lf\n",ans);
}
return 0;
}
分享到:
相关推荐
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
凸包经典入门,求凸包周长.00000000000000000000000
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
acm入门训练和日常训练 对于初学者以及acm爱好者有叫大帮助
hdu 1695 GCD(欧拉函数+容斥原理).docx
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
杭电ACMhdu1163
hdu1001解题报告
HDU的一题........HDU DP动态规
hdu 1574 passed sorce
acm hdu as easy as a+b
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241