POJ 3525 半平面交

news/2025/1/12 20:04:29/

题意:

求多边形的最大内接圆。

 

题解:

二分答案,将所有边向内部逼近,当面积为恰好0时即为最大半径

 

终于写a了一会。。

View Code
  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <cmath>
  7 
  8 #define N 222
  9 #define PI 3.14159265358979
 10 #define INF 1e9
 11 #define EPS 1e-7
 12 
 13 using namespace std;
 14 
 15 struct PO 
 16 {
 17     double x,y;
 18 }p[N],s[N],tp[N],f[N];
 19 
 20 struct LI
 21 {
 22     PO a,b;
 23 }li[N],sl[N];
 24 
 25 int n;
 26 
 27 inline void prt(PO &a)
 28 {
 29     printf("%lf    %lf\n",a.x,a.y);
 30 }
 31 
 32 inline void read()
 33 {
 34     for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
 35     p[1+n]=p[1];
 36 }
 37 
 38 inline int dc(double x)
 39 {
 40     if(x>EPS) return 1;
 41     else if(x<-EPS) return -1;
 42     return 0;
 43 }
 44 
 45 inline PO operator -(PO a,PO b)
 46 {
 47     PO c;
 48     c.x=a.x-b.x; c.y=a.y-b.y;
 49     return c;
 50 }
 51 
 52 inline PO rotate(PO a,double sss,double ccc)
 53 {
 54     PO ans;
 55     ans.x=ccc*a.x-sss*a.y;
 56     ans.y=sss*a.x+ccc*a.y;
 57     return ans;
 58 }
 59 
 60 inline double getlen(PO &a)
 61 {
 62     return sqrt(a.x*a.x+a.y*a.y);
 63 }
 64 
 65 inline PO getf(PO &a,PO &b)//得到ab左旋90度后的单位向量 
 66 {
 67     PO ans;
 68     ans=b-a;
 69     ans=rotate(ans,sin(0.5*PI),cos(0.5*PI));
 70     double k=getlen(ans);
 71     ans.x/=k; ans.y/=k;
 72     return ans;
 73 }
 74 
 75 inline void prep()
 76 {
 77     for(int i=1;i<=n;i++)
 78     {
 79         f[i]=getf(p[i],p[i+1]);
 80         li[i].a=p[i]; li[i].b=p[i+1];
 81     }
 82 }
 83 
 84 inline void move(double k)
 85 {
 86     for(int i=1;i<=n;i++)
 87     {
 88         sl[i].a.x=li[i].a.x+k*f[i].x;
 89         sl[i].a.y=li[i].a.y+k*f[i].y;
 90         sl[i].b.x=li[i].b.x+k*f[i].x;
 91         sl[i].b.y=li[i].b.y+k*f[i].y;
 92     }
 93 }
 94 
 95 inline double cross(PO &a,PO &b,PO &c)
 96 {
 97     return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
 98 }
 99 
100 inline PO getpoint(PO &a,PO &b,PO &c,PO &d)//直线交点 
101 {
102     PO ans,tp=b-a;
103     double k1=cross(a,d,c);
104     double k2=cross(b,c,d);
105     ans.x=a.x+tp.x*k1/(k1+k2);
106     ans.y=a.y+tp.y*k1/(k1+k2);
107     return ans;
108 }
109 
110 inline int getcut()
111 {
112     tp[1].x=tp[5].x=-INF; tp[1].y=tp[5].y=-INF;
113     tp[2].x=INF,tp[2].y=-INF;
114     tp[3].x=INF,tp[3].y=INF;
115     tp[4].x=-INF,tp[4].y=INF;
116     int cp=4,tc;
117     for(int i=1;i<=n;i++)
118     {
119         tc=0;
120         for(int j=1;j<=cp;j++)
121         {
122             if(dc(cross(sl[i].a,sl[i].b,tp[j]))>=0) s[++tc]=tp[j];
123             if(dc(cross(sl[i].a,sl[i].b,tp[j])*cross(sl[i].a,sl[i].b,tp[j+1]))<0)
124                 s[++tc]=getpoint(sl[i].a,sl[i].b,tp[j],tp[j+1]);
125         }
126         s[tc+1]=s[1];
127         for(int j=1;j<=tc+1;j++) tp[j]=s[j];
128         cp=tc;
129     }
130     return cp;
131 }
132 
133 inline void go()
134 {
135     prep();
136     double l=0.0,r=10000000.0,mid,ans;
137     int cs=100;
138     while(cs--)
139     {
140         mid=(l+r)*0.5;
141         move(mid);
142         if(getcut()) l=mid,ans=mid;
143         else r=mid;
144     }
145     printf("%.6lf\n",ans);
146 }
147 
148 int main()
149 {
150     while(scanf("%d",&n),n) read(),go();
151     return 0;
152 }

 

 

 

转载于:https://www.cnblogs.com/proverbs/archive/2013/02/27/2935894.html


http://www.ppmy.cn/news/163216.html

相关文章

亚马逊正常购物下单流程是怎么样的?

当您想要在亚马逊上购物时&#xff0c;您可以按照以下步骤进行&#xff1a; 1、登录亚马逊账户&#xff1a;在亚马逊的官方网站上&#xff0c;使用您的亚马逊账户进行登录。如果您还没有账户&#xff0c;可以在网站上注册一个新账户。 2、浏览商品&#xff1a;在亚马逊首页上&…

window环境下https证书本地部署

因为小程序要使用https的网址&#xff0c;本地localhost无法访问。为调试方使要使用https证书在公司局域网内访问。 1&#xff09;在阿里云或其他域名管理申请域名(z.abc.com)https证书,注意记录值是你本地局域网的IP&#xff0c;例如&#xff1a;192.168.2.11&#xff0c;这个…

航天航空飞机火箭模型3D打印制作服务/增材制造航空模型制作

3D打印是对“增材制造”这种材料成型工艺的通俗叫法。3D打印是制造业有代表性的颠覆性技术&#xff0c;区别于传统的材料成型工艺&#xff0c;在加工的过程中材料质量不减反增&#xff0c;通过“自下而上”的材料累加来成型。 【CASAIM智能制造】是中科院下属机构&#xff0c;作…

无法解析的外部符号 - 链接器工具错误 LNK2019, 竟然C/C++源文件.cpp未编译!

包含符号定义的源文件未编译 [中标] !!!! OC的.m文件修改为cpp文件, 导致包含符号定义的源文件未编译, 从而出现无法解析的外部符号 - 链接器工具错误 LNK2019. 找了半天时间. 特别注意, 以下内容是微软官方文档里面复制过来的: 本文内容 可能的原因第三方库问题和 vcpkg诊…

P1000

P1000 打印超级玛丽 图形 ********************####....#.#..###.....##....###.......###### ### ###........... #...# #...###*####### #.#.# #.#.#####*******###### #.#.# …

P1000 超级玛丽游戏c++

超级玛丽是一个非常经典的游戏。请你用字符画的形式输出超级玛丽中的一个场景。 ********************####....#.#..###.....##....###.......###### ### ###........... #...# #...###*####### #.#.# …

洛谷P1000 题解

洛谷P1000 题解 传送门 题意 输出字符画&#xff0c;详情见原题。 分析 本题直接输出&#xff0c;不用做任何读入和思考 代码 #include <bits/stdc.h> //万能头文件 using namespace std; //标准命名空间&#xff08;不加它你就用不了cin,cout&#xff09; int ma…

洛谷P1000 C++ 题解

文章目录 超级玛丽游戏题目背景题目描述输入格式输出格式分析AC代码 超级玛丽游戏 题目背景 本题是洛谷的试机题目&#xff0c;可以帮助了解洛谷的使用。 建议完成本题目后继续尝试 P1001、P1008。 另外强烈推荐新用户必读贴 题目描述 超级玛丽是一个非常经典的游戏。请你…