多边形内最大半径圆。
哇没有枉费了我自闭了这么些天，大概五天前我看到这种题可能毫无思路抓耳挠腮举手投降什么的，现在已经能1A了哇。
还是先玩一会计算几何，刷个几百道
嗯这个半平面交+二分就阔以解决。虽然队友说他施展三分套三分*****
想象一下，如果一个多边形能放进去半径为r的圆，那么在每条边向里平移r之后，他的内核一定不为空。
所以我们可以二分r，然后求半平面交，平移操作其实很好处理。
1A了很开森，去快乐的玩耍惹。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <deque>
using namespace std;
typedef double db;
const db eps=1e-;
const db pi=acos(-);
int sign(db k){
if (k>eps) return ; else if (k<-eps) return -; return ;
}
int cmp(db k1,db k2){return sign(k1-k2);}
struct point{
db x,y;
point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
point operator * (db k1) const{return (point){x*k1,y*k1};}
point operator / (db k1) const{return (point){x/k1,y/k1};}
db abs(){return sqrt(x*x+y*y);}
point unit(){db w=abs(); return point{x/w,y/w};}
point turn90(){ return point{-y,x};}
db getP()const { return sign(y)==||(sign(y)==&&sign(x)==-);}
};
db cross(point k1,point k2){ return k1.x*k2.y-k1.y*k2.x;}
db dot(point k1,point k2){ return k1.x*k2.x+k1.y*k2.y;}
db rad(point k1,point k2){ return atan2(cross(k1,k2),dot(k1,k2));}
int compareangle(point k1,point k2){
return k1.getP()<k2.getP()||(k1.getP()==k2.getP()&&sign(cross(k1,k2))>);
}
point getLL(point k1,point k2,point k3,point k4){
db w1=cross(k1-k3,k4-k3),w2=cross(k4-k3,k2-k3);
return (k1*w2+k2*w1)/(w1+w2);
}
struct line{
point p[];
line(point k1,point k2){p[]=k1;p[]=k2;}
point &operator[](int k){ return p[k];}
int include(point k){ return sign(cross(p[]-p[],k-p[])>);}
point dir(){ return p[]-p[];}
line push(db eps){//向左手边平移eps
//const db eps=1e-6;
point delta=(p[]-p[]).turn90().unit()*eps;
return {p[]-delta,p[]-delta};
}
};
point getLL(line k1,line k2){
return getLL(k1[],k1[],k2[],k2[]);
}
int parallel(line k1,line k2){ return sign(cross(k1.dir(),k2.dir()))==;}
int sameDir(line k1,line k2){
return parallel(k1,k2)&&sign(dot(k1.dir(),k2.dir()))==;
}
int operator <(line k1,line k2){
if(sameDir(k1,k2))return k2.include(k1[]);
return compareangle(k1.dir(),k2.dir());
}
int checkpos(line k1,line k2,line k3){ return k3.include(getLL(k1,k2));}
vector<line> getHL(vector<line> &L){
sort(L.begin(),L.end());deque<line> q;
for(int i=;i<L.size();i++){
if(i&&sameDir(L[i],L[i-]))continue;
while (q.size()>&&!checkpos(q[q.size()-],q[q.size()-],L[i]))q.pop_back();
while (q.size()>&&!checkpos(q[],q[],L[i]))q.pop_front();
q.push_back(L[i]);
}
while (q.size()>&&!checkpos(q[q.size()-],q[q.size()-],q[]))q.pop_back();
while (q.size()>&&!checkpos(q[],q[],q[q.size()-]))q.pop_front();
vector<line> ans;for(int i=;i<q.size();i++)ans.push_back(q[i]);
return ans;
}
point p[];
int n;
bool cw(){//时针
db s=;
for(int i=;i<n-;i++){
s+=cross(p[i]-p[],p[i+]-p[]);
}
return s>;
}
vector<line> L,tmp;
bool check(db x){
tmp.clear();
for(int i=;i<L.size();i++){
tmp.push_back(L[i].push(-x));
}
tmp = getHL(tmp);
if(tmp.size()>=)
return true;
return false;
}
int main(){
//freopen("3525.in","r",stdin);
while (scanf("%d",&n)&&n){
for(int i=;i<n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
if(!cw())reverse(p,p+n);
for(int i=;i<n;i++){
L.push_back(line(p[i],p[(i+)%n]));
}
db l = ,r=100000.0;
while (l+0.0000001<r){
db mid = (l+r)/;
if(check(mid))
l=mid;
else
r=mid;
}
printf("%.7f\n",l);
L.clear();
}
}