http://poj.org/problem?id=1113

不多说...凸包网上解法很多,这个是用graham的极角排序,也就是算导上的那个解法

其实其他方法随便乱搞都行...我只是测一下模板...

struct POINT{
double x,y;
POINT(double _x = , double _y = ):x(_x),y(_y){};
};
POINT p[MAXN],s[MAXN];
double dist(POINT p1,POINT p2){
return(sqrt((p1.x-p2.x) * (p1.x-p2.x) + (p1.y-p2.y) * (p1.y-p2.y)));
}
double multiply(POINT sp,POINT ep,POINT op){
return (sp.x-op.x) * (ep.y-op.y) - (ep.x-op.x) * (sp.y-op.y);
}
bool ptcmp(POINT a,POINT b){ // 极角排序cmp p[]为全局变量
if(multiply(a,b,p[]) == ) return dist(p[],a) < dist(p[],b);
return (multiply(a,b,p[]) > );
}
int Graham_scan(POINT p[],POINT s[],int n){ // 返回凸包点的个数
int i,k = ,top = ;
for(i = ; i < n ; i++) // 取y最小且x最小的点为凸包起点
if((p[i].y < p[k].y) || ((p[i].y == p[k].y) && (p[i].x < p[k].x)))
k = i;
swap(p[],p[k]); // 起点设置为p[0]
sort(p+,p+n,ptcmp); // 极角排序
for(i = ; i < ; i++)
s[i] = p[i]; // 前三个点入栈
for(i = ; i < n ; i++){
while(multiply(p[i],s[top],s[top-]) >= )
top--;
s[++top] = p[i];
}
return top + ;
}
int main()
{
int a,b,n;
double r;
while(~scanf("%d%lf",&n,&r)){
for(int i = ; i < n ; i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
int len = Graham_scan(p,s,n);
double sum = dist(s[len-],s[]);
for(int i = ; i < len- ; i++){
sum += dist(s[i],s[i+]);
}
sum += (PI*r*);
cout<<floor(sum+0.5)<<endl;
}
return ;
}

最新文章

  1. [Q&amp;A] VS 连接 SQLServer 时未找到或无法访问服务器
  2. Javascript获取随机数
  3. [译]git revert
  4. poj 1220(短除法)
  5. thymeleaf 中文乱码问题
  6. 用if else 判断是不是7的倍数等
  7. CentOS 七 vs CentOS 6的不同
  8. Android 自定义Activity栈对Activity统一管理
  9. 如何在Crystal框架项目中内置启动Zookeeper服务?
  10. Java中正则表达式去除html标签
  11. docker-compose编排项目redis容器实现主从复制
  12. 高级组件——表格模型TableModel
  13. SQL-49 针对库中的所有表生成select count(*)对应的SQL语句
  14. POI2014解题报告
  15. UML简单熟悉
  16. rsync安装及部署
  17. 通过 Spring Security配置 解决X-Frame-Options deny 造成的页面空白 iframe调用问题
  18. 【个人】爬虫实践,利用xpath方式爬取数据之爬取虾米音乐排行榜
  19. spinlock一边连逻辑一边连控制器
  20. [SharePoint 2010] SharePoint 2010 FBA 配置以及自定义首页

热门文章

  1. 基于MVC4+EasyUI的Web开发框架经验总结(13)--DataGrid控件实现自己主动适应宽带高度
  2. HDU 1512 左偏树+并查集
  3. 参加2012 Openstack亚太技术大会
  4. Python(九) Python的高级语法与用法
  5. 紫书 例题 9-2 UVa 437 ( DAG的动态规划)
  6. ttf字体转换成web中使用的woff、svg、eot格式字体
  7. JS jQuery查看系统中安装的字体
  8. LRJ入门经典-0907万圣节的小L306
  9. Mysql学习总结(2)——Mysql超详细Window安装教程
  10. CSUOJ 1637 Yet Satisfiability Again!