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

题目大意:给一个逆时针序列的多边形点集,求其中可以画的最大半径的圆的半径。

——————————————————————

二分枚举半径长度,然后将所有的边往内缩半径为r,求是否有内核即可。

#include<cstdio>
#include<queue>
#include<cctype>
#include<cstring>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double dl;
const dl eps=1e-;
const int N=;
struct Point{
dl x;
dl y;
}p[N],point[N],q[N],z;
//point,初始点
//q,暂时存可行点
//p,记录可行点
int n,curcnt,cnt;
//curcnt,暂时存可行点个数
//cnt,记录可行点个数
inline Point getmag(Point a,Point b){
Point s;
s.x=b.x-a.x;s.y=b.y-a.y;
return s;
}
inline dl multiX(Point a,Point b){
return a.x*b.y-b.x*a.y;
}
inline void getline(Point x,Point y,dl &a,dl &b,dl &c){
a=y.y-x.y;
b=x.x-y.x;
c=y.x*x.y-x.x*y.y;
return;
}
inline Point intersect(Point x,Point y,dl a,dl b,dl c){
Point s;
dl u=fabs(a*x.x+b*x.y+c);
dl v=fabs(a*y.x+b*y.y+c);
s.x=(x.x*v+y.x*u)/(u+v);
s.y=(x.y*v+y.y*u)/(u+v);
return s;
}
inline void cut(dl a,dl b,dl c){
curcnt=;
for(int i=;i<=cnt;i++){
if(a*p[i].x+b*p[i].y+c>-eps)q[++curcnt]=p[i];
else{
if(a*p[i-].x+b*p[i-].y+c>eps){
q[++curcnt]=intersect(p[i],p[i-],a,b,c);
}
if(a*p[i+].x+b*p[i+].y+c>eps){
q[++curcnt]=intersect(p[i],p[i+],a,b,c);
}
}
}
for(int i=;i<=curcnt;i++)p[i]=q[i];
p[curcnt+]=p[];p[]=p[curcnt];
cnt=curcnt;
return;
}
inline void init(){
for(int i=;i<=n;i++)p[i]=point[i];
z.x=z.y=;
p[n+]=p[];
p[]=p[n];
cnt=n;
return;
}
inline void regular(){//调换方向
for(int i=;i<(n+)/;i++)swap(point[i],point[n-i]);
return;
}
inline bool solve(dl r){
init();
for(int i=;i<=n;i++){
Point ta,tb,tt;
tt.x=point[i+].y-point[i].y;
tt.y=point[i].x-point[i+].x;
dl k=r/sqrt(tt.x*tt.x+tt.y*tt.y);
tt.x*=k;tt.y*=k;
ta.x=point[i].x+tt.x;
ta.y=point[i].y+tt.y;
tb.x=point[i+].x+tt.x;
tb.y=point[i+].y+tt.y;
dl a,b,c;
getline(ta,tb,a,b,c);
cut(a,b,c);
}
return cnt;
}
int main(){
while(scanf("%d",&n)!=EOF&&n){
for(int i=;i<=n;i++){
scanf("%lf%lf",&point[i].x,&point[i].y);
}
regular();
point[n+]=point[];
dl l=,r=;
while(fabs(l-r)>eps){
dl mid=(l+r)/2.0;
if(solve(mid))l=mid;
else r=mid;
}
printf("%.6f\n",l);
}
return ;
}

最新文章

  1. Sharepoint学习笔记—习题系列--70-573习题解析 -(Q139-Q141)
  2. HNU 12869 Sequence(循环节)
  3. Linux架构
  4. java获得当前文件路径
  5. [转]Linux之type命令
  6. php中常用设置
  7. WebSphere应用服务器中https 请求协议的相关注意事项(服务器使用代理上Internet)
  8. NOI十连测 第五测 T1
  9. Scala Tuple类型
  10. Struts2学习笔记(五)——Action访问Servlet API
  11. 在servlet中使用@Autowired注解无法注入实例的问题
  12. java 三大框架
  13. scss 初学笔记 二 混合宏
  14. 2.表单与PHP
  15. tensorflow 升级后报错:ImportError: libcudnn.so.6: cannot open shared object file: No such file or directory
  16. Android studio3.1.3 打包jar,混淆
  17. Maven Speed Up
  18. HyperLedger/Fabric SDK使用Docker容器镜像快速部署上线
  19. Ubuntu14设置静态IP的地方
  20. C++ 定时器Timer在项目中的使用

热门文章

  1. POM中常用依赖包
  2. MyBatis-SELECT基本查询
  3. Odd CSS syntax. [class^=&#39;icon-&#39;], [class*=&#39; icon-&#39;]
  4. 【springmvc+mybatis项目实战】杰信商贸-4.maven依赖+PO对+映射文件
  5. 孤荷凌寒自学python第八十二天学习爬取图片2
  6. Idea Live Templates
  7. 拥抱移动端,jQueryui触控设备兼容插件
  8. logisitic回归
  9. Python3 Tkinter-Frame
  10. SpringCloud IDEA 教学 (一) Eureka的简介与服务注册中心的建立