博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 1113 Wall(凸包)
阅读量:5815 次
发布时间:2019-06-18

本文共 934 字,大约阅读时间需要 3 分钟。

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

题意:给定多边形城堡的n个顶点,绕城堡外面建一个围墙,围住所有点,并且墙与所有点的距离至少为L,求这个墙最小的长度。

 

公式:

城堡围墙长度最小值 = 城堡顶点坐标构成的散点集的凸包总边长 + 半径为L的圆周长

View Code
1 #include 
2 #include
3 #include
4 #include
5 #define PI 3.1415926535 6 using namespace std; 7 const double eps=1e-6; 8 typedef struct node 9 {10 int x,y;11 }point;12 int n;13 point pt[1100];14 point res[1100];15 bool cmp(point a,point b)16 {17 if(a.x==b.x)18 return a.y
1&&cross(res[m-1],pt[i],res[m-2])<=0)58 m--;59 res[m++]=pt[i];60 }61 int k=m;62 for(i=n-2;i>=0;i--)63 {64 while(m>k&&cross(res[m-1],pt[i],res[m-2])<=0)65 m--;66 res[m++]=pt[i];67 }68 if(n>1)69 m--;70 double dis=0;71 for(i=0;i

 

转载于:https://www.cnblogs.com/wanglin2011/archive/2013/03/08/2950381.html

你可能感兴趣的文章
PHP垃圾回收机制
查看>>
linux socket网络编程 线程池实现客服端程序
查看>>
thinkphp5中的一些关于命名空间的tisp
查看>>
[NIO-3]Socket通道
查看>>
ios之UILabel
查看>>
第6章-装饰模式
查看>>
CSRF与XSS攻击的原理与防范
查看>>
Java基础之String,StringBuilder,StringBuffer
查看>>
狼图腾读后感
查看>>
1月9日学习内容整理:爬虫基本原理
查看>>
根据百度API获得经纬度,然后根据经纬度在获得城市信息
查看>>
安卓中数据库的搭建与使用
查看>>
php 通过stomp协议连接ActiveMQ
查看>>
Review1-11
查看>>
AT3908 Two Integers
查看>>
渐变色文字
查看>>
JS找出一串字符中出现最多的字符
查看>>
C++ 0X 新特性实例(比较常用的) (转)
查看>>
node生成自定义命令(yargs/commander)
查看>>
各种非算法模板
查看>>