二维几何基础

1. 点、线、凸边形

/*******************************************************
                    二维几何基础
【注意】数组下标从1开始。
*******************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <string>
#define re register
#define il inline
#define ll long long
#define ld long double
using namespace std;
const ll MAXN = 1e5+5;
const ll INF = 1e9;
const ld EPS = 1e-9;
 
//点坐标
struct POINT
{
    ld x, y;
    POINT() : x(0), y(0) {}
    POINT(ld _x, ld _y) : x(_x), y(_y) {}
};
//向量
typedef POINT VECTOR;
 
POINT xy[MAXN];     //顺时针多边形顶点存储
POINT xyB[MAXN];    //判断点存储
 
 
//符号函数
ll sgn(ld x)    {return x < -EPS ? -1 : x > EPS;}
//向量+向量=向量，点+向量=点
VECTOR operator + (VECTOR a, VECTOR b)  {return {a.x+b.x,a.y+b.y};}
//向量-向量=向量，点-点=向量
VECTOR operator - (VECTOR a, VECTOR b)  {return {a.x-b.x,a.y-b.y};}
//向量*数=向量
VECTOR operator * (VECTOR a, ld k)  {return {a.x*k,a.y*k};}
VECTOR operator * (ld k, VECTOR a)  {return {a.x*k,a.y*k};}
//向量/数=向量
VECTOR operator / (VECTOR a, ld k)  {return {a.x/k,a.y/k};}
//向量==向量，点==点
bool operator == (const VECTOR a, const VECTOR b)   {return !sgn(a.x-b.x) && !sgn(a.y-b.y);}
//向量偏序关系（先x轴再y轴）
bool operator < (const VECTOR a, const VECTOR b)    {return !sgn(a.x-b.x) ? a.y < b.y : a.x < b.x;}
//向量旋转（逆时针）
VECTOR rot(VECTOR a, ld sita)   {return {a.x*cos(sita)-a.y*sin(sita),a.x*sin(sita)+a.y*cos(sita)};}
//取下端点
POINT min(POINT p1, POINT p2)   {return p1.y<p2.y ? p1:p2;}
//取上端点
POINT max(POINT p1, POINT p2)   {return p1.y<p2.y ? p2:p1;}
//点积
ld dot(POINT p1, POINT p2, POINT p) {return (p.x-p1.x)*(p2.x-p1.x)+(p.y-p1.y)*(p2.y-p1.y);} //（三点式：共p1端点）
ld dot(VECTOR a, VECTOR b)      {return a.x*b.x+a.y*b.y;}   //向量式
//叉积
ld cross(POINT p1, POINT p2, POINT p)   {return (p.x-p1.x)*(p2.y-p1.y)-(p.y-p1.y)*(p2.x-p1.x);} //（三点式：共p1端点）
ld cross(VECTOR a, VECTOR b)    {return a.x*b.y-a.y*b.x;}   //向量式（aXb）
//向量长度
ld vlen(VECTOR a) {return sqrt(dot(a,a));}
//向量夹角余弦值
ld vcos(VECTOR a, VECTOR b) {return dot(a,b)/(vlen(a)*vlen(b));}
//向量夹角正弦值
ld vsin(VECTOR a, VECTOR b) {return fabs(cross(a,b))/(vlen(a)*vlen(b));}
//向量极角
ld vagl(VECTOR a, VECTOR b) {return acos(dot(a,b)/(vlen(a)*vlen(b)));}  //向量间
ld vagl(VECTOR a) {return acos(a.x/vlen(a));}
//求直线斜率【注意】确保斜率存在
ld slope(VECTOR a)  {return a.y/a.x;}   //向量式
ld slope(POINT p, POINT q)  {return (p.y-q.y)/(p.x-q.x);}   //两点式
//单位向量【注意】确保非零向量
VECTOR unit(VECTOR a)   {return a/vlen(a);}
//两直线交点
POINT intersectline(POINT p, VECTOR v, POINT q, VECTOR w)   {return p+v*cross(w,p-q)/cross(v,w);}   //（参数式：P=P0+t*v，P0为直线上某一点，v为直线的方向向量）
//点在直线上的投影
POINT proline(POINT a, POINT b, POINT p)	{return a+(b-a)*(dot(b-a,p-a)/dot(b-a,b-a));}
//点关于直线的对称点
POINT refline(POINT a, POINT b, POINT p)	{return proline(a,b,p)*2-p;}
//判断两直线是否平行
bool parallel(POINT p1, POINT p2, POINT q1, POINT q2)   {return !sgn(cross(p2-p1,q2-q1)) && sgn(cross(p1-q1,p2-q1));}
//判断两直线重合
bool superposition(POINT p1, POINT p2, POINT q1, POINT q2)  {return !sgn(cross(p2-p1,q2-q1)) && !sgn(cross(p1-q1,p2-q1));}
//点到直线距离
ld disline(POINT a, POINT b, POINT p)   {return fabs(cross(b-a,p-a))/vlen(b-a);}    //不取绝对值得到的是有向距离
//点到线段距离（两种情况：点的投影在线段上，则为垂直距离；点的投影不在线段上，则为到两端距离的最小值）
ld disseg(POINT a, POINT b, POINT p)    {return a==b ? vlen(p-a):dot(b-a,p-a)<0 ? vlen(p-a):dot(b-a,p-b)>0 ? vlen(p-b):fabs(cross(b-a,p-a))/vlen(b-a);}
//线段相交判断（严格）
bool intersectseg(POINT p1, POINT p2, POINT q1, POINT q2)   {return cross(p1-q1,q2-q1)*cross(p2-q1,q2-q1)<0 && cross(q1-p1,p2-p1)*cross(q2-p1,p2-p1)<0;}
//判断点p(x,y)是否在线段p1p2上（两种情况：1.包括端点；2.不包含端点）
bool onseg(POINT p1, POINT p2, POINT p) {return !sgn(cross(p1,p2,p)) && sgn(dot(p,p1,p2))<=0;}  //包含端点
bool onseg_strict(POINT p1, POINT p2, POINT p)  {return !sgn(cross(p1,p2,p)) && sgn(dot(p,p1,p2))<0;}   //不包含端点
 
//点射法判断点是否在多边形内部（边界也算在内部）
//复杂度O(n)（不论凹凸）
bool inpolygon_dot(ld x, ld y, ll n)
{
    ll cnt = 0;
    for(re ll i = 0; i < n; ++i)
    {
        POINT p1 = min(xy[i+1], xy[(i+1)%n+1]);    //取下端点
        POINT p2 = max(xy[i+1], xy[(i+1)%n+1]);    //取上端点
        //特判点在线段上
        if(onseg(p1,p2,{x,y}))    return true;
        //从点(x,y)向x反方向引出射线
        //计算点射到的多边形的边数边数
        if(sgn(p1.y-y)<0 && sgn(y-p2.y) <=0 && sgn(cross(p1,p2,{x,y}))>0)   ++cnt;
    }
    if(cnt%2)   return true;
    else    return false;
}
 
//二分法判断点是否在多边形内部（不包括边界）
//复杂度O(logn)（要求凸多边形）
bool inpolygon_bis(ld x, ld y, ll n)
{
    POINT p = {x,y};
    ll l = 2, r = n;
    //判断是否在幅角最小和最大的两条边上
    if(onseg(xy[1],xy[l],p) || onseg(xy[1],xy[n],p))    return false;
    //二分法判断是否在多边形内部
    while(l < r)
    {
        ll mid = (l+r)>>1;  //【注意】如此取中点最终：r==l或r==l-1（只有此两种情况）
        ll d = sgn(cross(xy[mid]-xy[1],p-xy[1]));
        if(d < 0)   l = mid+1;
        else if(d > 0)  r = mid-1;
        else
        {
            if(onseg_strict(xy[1],xy[mid],p))
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
    //判断在最终二分得到的对角线两端的边是否都满足严格在内的条件
    if(l >= r && (sgn(cross(xy[l]-xy[l-1],p-xy[l-1]))>=0 || sgn(cross(xy[l%n+1]-xy[l],p-xy[l]))>=0))
    {
        return false;
    }
    return true;
}
 
//计算多边形面积（凹凸均可）
ld polygonarea(ll n)
{
    ld aera = 0;
    for(re ll i = 0; i < n; ++i)
    {
        aera += cross(xy[i+1], xy[(i+1)%n+1]);
    }
    //计算出来的aera为有向面积
    return fabs(aera)/2;
}
 
int main()
{
    std::ios::sync_with_stdio(false);
	//判断直线平行/重合/相交
    ll n;
    cin >> n;
    cout << "INTERSECTING LINES OUTPUT" << endl;
    for(re ll i = 1; i <= n; ++i)
    {
        POINT p1, p2, p3, p4;
        cin >> p1.x >> p1.y >> p2.x >> p2.y;
        cin >> p3.x >> p3.y >> p4.x >> p4.y;
        if(parallel(p1,p2,p3,p4))   cout << "NONE" << endl;
        else if(superposition(p1,p2,p3,p4)) cout << "LINE" << endl;
        else
        {
            POINT q = intersectline(p1,p2-p1,p3,p4-p3);
            cout << "POINT " << fixed << setprecision(2) << q.x << " " << q.y << endl;
        }
    }
    cout << "END OF OUTPUT" << endl;
    return 0;
    /*
    //计算多边形的面积
    ll n;
    while(true)
    {
        std::cin >> n;
        if(!n)  break;
        for(re ll i = 1; i <= n; ++i)
        {
            std::cin >> xy[i].x;
            std::cin >> xy[i].y;
        }
        std::cout << std::fixed << std::setprecision(1) << polygonarea(n) << std::endl;
    }
    return 0;
    */
	/*
    //判断点是否在多边形内（不包括边界）
    ll n;
    std::cin >> n;
    for(re ll i = 1; i <= n; ++i)
    {
        std::cin >> xy[i].x;
        std::cin >> xy[i].y;
    }
    ll m;
    cin >> m;
    for(re ll i = 1; i <= m; ++i)
    {
        cin >> xyB[i].x;
        cin >> xyB[i].y;
    }
    for(re ll i = 1; i <= m; ++i)
    {
        if(!inpolygon_bis(xyB[i].x, xyB[i].y, n))
        {
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
    return 0;
	*/
    /*
    //判断点是否在多边形内（包括边界）
    ll N, M, k = 0;
    while(!(std::cin >> N).eof())
    {
        if(!N)  break;
        std::cin >> M;
        if(k)   printf("\n");
        ++k;
        for(re ll i = 1; i <= N; ++i)
        {
            std::cin >> xy[i].x;
            std::cin >> xy[i].y;
            //printf("(%f,%f)\n", xy[i].x, xy[i].y);
        }
        printf("Problem %lld:\n", k);
        for(re ll i = 1; i <= M; ++i)
        {
            ld x, y;
            std::cin >> x;
            std::cin >> y;
            //printf("(%f,%f)\n", x, y);
            if(inpolygon(x, y, N))
            {
                printf("Within\n");
            }
            else
            {
                printf("Outside\n");
            }
        }
    }
    return 0;
    */
}

2. 圆

/*****************************************************************
                            圆
【注意】三角与反三角最多用一次（损失精度大）。
*****************************************************************/
 
#include <bits/stdc++.h>
#include <iomanip>
#include <stack>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define re register
#define il inline
#define ll long long
#define ld long double
using namespace std;
const ld PI = 3.14159265358979323846;
const ll MAXN = 5e5+5;
const ld INF = 1e9;
const ld EPS = 1e-10;
 
//点坐标
struct POINT
{
    ld x, y;
    POINT() : x(0), y(0) {}
    POINT(ld _x, ld _y) : x(_x), y(_y) {}
};
//向量
typedef POINT VECTOR;
 
//符号函数
ll sgn(ld x)    {return x < -EPS ? -1 : x > EPS;}
//向量+向量=向量，点+向量=点
VECTOR operator + (VECTOR a, VECTOR b)  {return {a.x+b.x,a.y+b.y};}
//向量-向量=向量，点-点=向量
VECTOR operator - (VECTOR a, VECTOR b)  {return {a.x-b.x,a.y-b.y};}
//向量*数=向量
VECTOR operator * (VECTOR a, ld k)  {return {a.x*k,a.y*k};}
VECTOR operator * (ld k, VECTOR a)  {return {a.x*k,a.y*k};}
//向量/数=向量
VECTOR operator / (VECTOR a, ld k)  {return {a.x/k,a.y/k};}
//向量==向量，点==点
bool operator == (const VECTOR a, const VECTOR b)   {return !sgn(a.x-b.x) && !sgn(a.y-b.y);}
//向量偏序关系（先x轴再y轴）
bool operator < (const VECTOR a, const VECTOR b)    {return !sgn(a.x-b.x) ? a.y < b.y : a.x < b.x;}
//取下端点
POINT min(POINT p1, POINT p2)   {return p1.y<p2.y ? p1:p2;}
//取上端点
POINT max(POINT p1, POINT p2)   {return p1.y<p2.y ? p2:p1;}
//点积
ld dot(POINT p1, POINT p2, POINT p) {return (p.x-p1.x)*(p2.x-p1.x)+(p.y-p1.y)*(p2.y-p1.y);} //（三点式：共p1端点）
ld dot(VECTOR a, VECTOR b)      {return a.x*b.x+a.y*b.y;}   //向量式
//叉积
ld cross(POINT p1, POINT p2, POINT p)   {return (p.x-p1.x)*(p2.y-p1.y)-(p.y-p1.y)*(p2.x-p1.x);} //（三点式：共p1端点）
ld cross(VECTOR a, VECTOR b)    {return a.x*b.y-a.y*b.x;}   //向量式（aXb）
//向量长度
ld vlen(VECTOR a) {return sqrt(dot(a,a));}
//向量旋转（逆时针）
VECTOR rot(VECTOR a, ld sita)   {return {a.x*cos(sita)-a.y*sin(sita),a.x*sin(sita)+a.y*cos(sita)};}
//取单位向量
VECTOR unit(VECTOR a)   {return a/vlen(a);}
//取正交单位向量
VECTOR norm(VECTOR a)   {return VECTOR(-a.y,a.x)/vlen(a);}
//向量夹角余弦值
ld vcos(VECTOR a, VECTOR b) {return dot(a,b)/(vlen(a)*vlen(b));}
//向量夹角正弦值
ld vsin(VECTOR a, VECTOR b) {return fabs(cross(a,b))/(vlen(a)*vlen(b));}
//向量极角
//【注意】使用系统反三角函数返回nan是因为超出了定义域（大多数由于精度造成）
//【注意】故使用系统反三角函数需处理边界
ld vagl(VECTOR a, VECTOR b)
{
    ld d = dot(a,b)/(vlen(a)*vlen(b));
    if(sgn(d-1) == 0)   return 0;
    else if(sgn(d+1) == 0)  return PI;
    else    return acos(d);
}  //向量间[0,PI]
ld vagl(VECTOR a) {return atan2(a.y, a.x);}                 //单向量[-PI,PI]
 
//直线
struct LINE
{
    POINT p;   //直线上定点
    VECTOR v;   //直线方向向量
    LINE() {}
    //点向式
    LINE(POINT _p, VECTOR _v):p(_p), v(_v) {}
    //点角式
    LINE(POINT _p, ld a):p(_p), v(VECTOR(cos(a), sin(a))) {}
    //通过参数t唯一确定直线上点坐标（点向式：P = p + t*v）
    POINT point(ld t)   {return p + t*v;}
    //平移向量r
    LINE trans(VECTOR r)    {return LINE(p+r,v);}
};
 
//点到直线距离
ld PLdist(POINT p, LINE L) {return fabs(sin(vagl(p-L.p,L.v))*vlen(p-L.p));}
 
//圆
struct CIRCLE
{
    POINT c;        //圆心坐标
    ld r;           //半径
    CIRCLE() {}
    CIRCLE(POINT _c, ld _r):c(_c),r(_r) {}
    //通过圆心角唯一确定圆上点坐标
    POINT point(ld a)   //a为圆心角
    {
        return POINT(c.x+cos(a)*r, c.y+sin(a)*r);
    }
};
 
//两点中垂线
//返回中垂线的个数
ll PerpendicularBisector(POINT p1, POINT p2, LINE &L)
{
    if(p1 == p2)    return 0;
    L.p = (p1+p2)/2;
    L.v = rot(p2-p1, PI/2);
    return 1;
}
 
//两直线交点
POINT LLitesct;
 
//直线与直线的交点
//返回交点个数
ll LineLineIntersection(LINE L1, LINE L2, POINT &p)
{
    if(sgn(cross(L1.v, L2.v)) == 0)
    {
        if(sgn(cross(L2.p-L1.p,L2.v) == 0))    return -1;          //两直线重合
        else    return 0;                       //两直线平行
    }
    //以L1为准
    ld t1 = -cross(L2.p-L1.p, L2.v)/cross(L2.v, L1.v);
    p = L1.p + t1*L1.v;
    //以L2为准
    //ld t2 = -cross(L1.p-L2.p, L1.v)/cross(L1.v, L2.v);
    //p = L2.p + t2*L2.v;
    return 1;
}
 
//直线与圆交点数组
vector <POINT> LCitesct;
 
//直线与圆的交点
//解方程：(at+b)^2+(ct+d)^2 = r^2;
//化简得：et^2+ft+g = 0
//返回交点个数
ll LineCircleIntersection(LINE L, CIRCLE C, ld &t1, ld &t2, vector <POINT>& sol)
{
    ld a = L.v.x, b = L.p.x-C.c.x, c = L.v.y, d = L.p.y-C.c.y;
    ld e = a*a + c*c, f = 2*(a*b + c*d), g = b*b + d*d - C.r*C.r;
    ld delta = f*f - 4*e*g;
    if(sgn(delta) < 0)          //相离
        return 0;
    else if(sgn(delta) == 0)    //相切
    {
        t1 = t2 = -f/(2*e);
        sol.push_back(L.point(t1));
        return 1;
    }
    else
    {
        t1 = (-f - sqrt(delta))/(2*e);
        t2 = (-f + sqrt(delta))/(2*e);
        sol.push_back(L.point(t1));
        sol.push_back(L.point(t2));
        return 2;
    }
}
ll LineCircleIntersection(LINE L, CIRCLE C, POINT *p)
{
    ld t1, t2;
    ld a = L.v.x, b = L.p.x-C.c.x, c = L.v.y, d = L.p.y-C.c.y;
    ld e = a*a + c*c, f = 2*(a*b + c*d), g = b*b + d*d - C.r*C.r;
    ld delta = f*f - 4*e*g;
    if(sgn(delta) < 0)          //相离
        return 0;
    else if(sgn(delta) == 0)    //相切
    {
        t1 = t2 = -f/(2*e);
        p[0] = L.point(t1);
        return 1;
    }
    else
    {
        t1 = (-f - sqrt(delta))/(2*e);
        t2 = (-f + sqrt(delta))/(2*e);
        p[0] = L.point(t1);
        p[1] = L.point(t2);
        return 2;
    }
}
 
//圆与圆的交点数组
vector <POINT> CCitesct;
 
//两圆交点
ll CircleCircleIntersection(CIRCLE C1, CIRCLE C2, vector <POINT>& sol)
{
    ld d = vlen(C1.c-C2.c);
    if(sgn(d) == 0)
    {
        if(sgn(C1.r-C2.r) == 0) return -1;          //两圆重合
        else    return 0;                           //同心相含
    }
    if(sgn(C1.r+C2.r-d) < 0)    return 0;           //相离
    if(sgn(fabs(C1.r-C2.r)-d) > 0)  return 0;       //异心相含
 
    //设两圆交点为p1,p2
    ld a = vagl(C2.c - C1.c);                       //向量C1C2的极角
    ld b = acos((C1.r*C1.r + d*d - C2.r*C2.r)/(2*C1.r*d));  //向量C1C2到C1P1（或C1P2）的夹角
    POINT p1 = C1.point(a-b);
    POINT p2 = C1.point(a+b);
    sol.push_back(p1);
    if(p1 == p2)    return 1;                       //相切
    sol.push_back(p2);                              //相交
    return 2;
}
 
//圆切线方向向量
VECTOR LCtgt[2];
 
//过定点作圆的切线
ll Tangents(POINT p, CIRCLE C, VECTOR *v)
{
    VECTOR u = C.c - p;
    ld dist = vlen(u);
    if(dist < C.r)  return 0;       //点在圆内，没有切线
    else if(sgn(dist-C.r) == 0)     //点在圆上，一条切线
    {
        v[0] = rot(u, PI/2);
        return 1;
    }
    else                            //点在圆外，两条切线
    {
        ld a = asin(C.r/dist);
        v[0] = rot(u, -a);
        v[1] = rot(u, +a);
        return 2;
    }
}
 
//两圆公切点（分别在两圆上）
POINT CCtgt1[4], CCtgt2[4];
 
//两圆公切线
ll Tangents(CIRCLE C1, CIRCLE C2, POINT *a, POINT *b)
{
    ll cnt = 0;
    if(C1.r < C2.r) {swap(C1, C2); swap(a, b);}
    ld d = dot(C1.c-C2.c, C1.c-C2.c);
    ld rdiff = C1.r - C2.r;
    ld rsum = C1.r + C2.r;
    if(d < rdiff*rsum)  return 0;                       //相含
    ld base = atan2(C2.c.y-C1.c.y, C2.c.x-C1.c.x);      //向量C1C2极角[-PI,PI]
    if(sgn(d) == 0 && sgn(C1.r-C2.r) == 0)  return -1;  //重合
    if(sgn(d-rdiff*rdiff) == 0)                         //内切
    {
        a[cnt] = C1.point(base);
        b[cnt++] = C2.point(base);
        return 1;
    }
    ld ang = acos((C1.r-C2.r)/sqrt(d));                 //夹角[0,PI]
    a[cnt] = C1.point(base+ang);
    b[cnt++] = C2.point(base+ang);
    a[cnt] = C1.point(base-ang);
    b[cnt++] = C2.point(base-ang);
    if(sgn(d-rsum*rsum))                                //外切
    {
        a[cnt] = C1.point(base);
        b[cnt++] = C2.point(base+PI);
    }
    else if(d > rsum*rsum)                              //相离
    {
        ld ang = acos((C1.r+C2.r)/sqrt(d));
        a[cnt] = C1.point(base+ang);
        b[cnt++] = C2.point(base+ang);
        a[cnt] = C1.point(base-ang);
        b[cnt++] = C2.point(base-ang);
    }
    return cnt;                                         //切点个数
}
 
//三点外接圆
//返回外接圆的个数
ll CircumscribedCircle(POINT a, POINT b, POINT c, CIRCLE &C)
{
    if(sgn(cross(a-b, b-c)) == 0)   return 0;           //三点共线
    LINE L1, L2;
    PerpendicularBisector(a, b, L1);
    PerpendicularBisector(b, c, L2);
    POINT p;
    LineLineIntersection(L1, L2, p);
    C.c = p;
    C.r = vlen(p-a);
    return 1;
}
 
//三点内接圆
//返回内接圆的个数
ll InscribedCircle(POINT a, POINT b, POINT c, CIRCLE &C)
{
    if(sgn(cross(a-b, b-c)) == 0)   return 0;           //三点共线
    LINE L1 = LINE(a, (vagl(b-a)+vagl(c-a))/2), L2 = LINE(b, (vagl(a-b)+vagl(c-b))/2);
    POINT p;
    LineLineIntersection(L1, L2, p);
    C.c = p;
    C.r = PLdist(p,LINE(a,b-a));
    return 1;
}
 
 
int main()
{
    //UVA-12304
    //ios::sync_with_stdio(false);
    string str;
    while(cin >> str)
    {
        if(str == "CircumscribedCircle")
        {
            POINT a, b, c;
            cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
            CIRCLE C;
            CircumscribedCircle(a,b,c,C);
            cout << fixed << "(" << C.c.x << "," << C.c.y << "," << C.r << ")" << endl;
        }
        else if(str == "InscribedCircle")
        {
            POINT a, b, c;
            cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
            CIRCLE C;
            InscribedCircle(a,b,c,C);
            cout << fixed << "(" << C.c.x << "," << C.c.y << "," << C.r << ")" << endl;
        }
        //求已知圆的切线的极角
        else if(str == "TangentLineThroughPoint")
        {
            CIRCLE C;
            POINT p;
            cin >> C.c.x >> C.c.y >> C.r >> p.x >> p.y;
            VECTOR v[2];
            ll cnt = Tangents(p,C,v);
            cout << "[";
            if(cnt == 1)
            {
                ld r = vagl(v[0]);
                ld a = (sgn(r) < 0 ? PI+r : sgn(r-PI) == 0 ? 0 : r)*180/PI;
                cout << fixed << a;
            }
            else if(cnt == 2)
            {
                ld mxr = vagl(v[0]);
                ld mir = vagl(v[1]);
                ld mxa = (sgn(mxr) < 0 ? PI+mxr : sgn(mxr-PI) == 0 ? 0 : mxr)*180/PI;
                ld mia = (sgn(mir) < 0 ? PI+mir : sgn(mir-PI) == 0 ? 0 : mir)*180/PI;
                if(mxa < mia)   swap(mxa,mia);
                cout << fixed << mia << "," << mxa;
            }
            cout << "]" << endl;
        }
        //求过定点且与已知直线相切的圆的圆心
        else if(str == "CircleThroughAPointAndTangentToALineWithRadius")
        {
            CIRCLE P;
            POINT p1, p2;
            cin >> P.c.x >> P.c.y >> p1.x >> p1.y >> p2.x >> p2.y >> P.r;
            VECTOR v = rot(p2-p1,PI/2);
            ld t = P.r/vlen(v);
            LINE L1 = LINE(p1+t*v,p2-p1), L2 = LINE(p1-t*v,p2-p1);
            ll cnt = 0;
            ld t1, t2;
            vector <POINT> C;
            cnt += LineCircleIntersection(L1,P,t1,t2,C);
            cnt += LineCircleIntersection(L2,P,t1,t2,C);
            sort(C.begin(),C.end());
            cout << "[";
            if(cnt == 1)    cout << fixed << "(" << C[0].x << "," << C[0].y << ")";
            else if(cnt == 2)   cout << fixed << "(" << C[0].x << "," << C[0].y << ")" << "," << "(" << C[1].x << "," << C[1].y << ")";
            cout << "]" << endl;
        }
        //求给定半径且与两条不相交直线相切的圆的圆心
        else if(str == "CircleTangentToTwoLinesWithRadius")
        {
            POINT p1, p2, p3, p4;
            ld r;
            cin >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y >> p4.x >> p4.y >> r;
            LINE L1 = LINE(p1,p2-p1), L2 = LINE(p3,p4-p3);
            VECTOR v1 = norm(p2-p1), v2 = norm(p4-p3);
            LINE L11 = L1.trans(r*v1), L12 = L1.trans(-r*v1);
            LINE L21 = L2.trans(r*v2), L22 = L2.trans(-r*v2);
            vector <POINT> C;
            POINT p;
            LineLineIntersection(L11,L21,p);
            C.push_back(p);
            LineLineIntersection(L11,L22,p);
            C.push_back(p);
            LineLineIntersection(L12,L21,p);
            C.push_back(p);
            LineLineIntersection(L12,L22,p);
            C.push_back(p);
            sort(C.begin(),C.end());
            cout << "[";
            cout << fixed << "(" << C[0].x << "," << C[0].y << ")" << "," << "(" << C[1].x << "," << C[1].y << ")" << ",";
            cout << fixed << "(" << C[2].x << "," << C[2].y << ")" << "," << "(" << C[3].x << "," << C[3].y << ")";
            cout << "]" << endl;
 
        }
        else if(str == "CircleTangentToTwoDisjointCirclesWithRadius")
        {
            CIRCLE C1, C2;
            ld r;
            cin >> C1.c.x >> C1.c.y >> C1.r >> C2.c.x >> C2.c.y >> C2.r >> r;
            C1.r += r, C2.r += r;
            vector <POINT> p;
            ll cnt = CircleCircleIntersection(C1,C2,p);
            sort(p.begin(),p.end());
            cout << "[";
            if(cnt == 1)
            {
                cout << fixed << "(" << p[0].x << "," << p[0].y << ")";
            }
            else if(cnt == 2)
            {
                cout << fixed << "(" << p[0].x << "," << p[0].y << ")" << "," << "(" << p[1].x << "," << p[1].y << ")";
            }
            cout << "]" << endl;
        }
    }
    return 0;
}

3. 半平面

/*****************************************************************
                            半平面交
【注意】三角与反三角最多用一次（损失精度大）。
【注意】数组下标一律从1开始。
*****************************************************************/
 
//#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <stack>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define re register
#define il inline
#define ll int
#define ld double
using namespace std;
const ld PI = 3.14159265358979323846;
const ll MAXN = 5e5+5;
const ld INF = 1e9;
const ld EPS = 1e-8;
 
//点坐标
struct POINT
{
    ld x, y;
    POINT() : x(0), y(0) {}
    POINT(ld _x, ld _y) : x(_x), y(_y) {}
};
//向量
typedef POINT VECTOR;
 
//符号函数
ll sgn(ld x)    {return x < -EPS ? -1 : x > EPS;}
//向量+向量=向量，点+向量=点
VECTOR operator + (VECTOR a, VECTOR b)  {return {a.x+b.x,a.y+b.y};}
//向量-向量=向量，点-点=向量
VECTOR operator - (VECTOR a, VECTOR b)  {return {a.x-b.x,a.y-b.y};}
//向量*数=向量
VECTOR operator * (VECTOR a, ld k)  {return {a.x*k,a.y*k};}
VECTOR operator * (ld k, VECTOR a)  {return {a.x*k,a.y*k};}
//向量/数=向量
VECTOR operator / (VECTOR a, ld k)  {return {a.x/k,a.y/k};}
//向量==向量，点==点
bool operator == (const VECTOR a, const VECTOR b)   {return !sgn(a.x-b.x) && !sgn(a.y-b.y);}
//向量偏序关系（先x轴再y轴）
bool operator < (const VECTOR a, const VECTOR b)    {return !sgn(a.x-b.x) ? a.y < b.y : a.x < b.x;}
//取下端点
POINT min(POINT p1, POINT p2)   {return p1.y<p2.y ? p1:p2;}
//取上端点
POINT max(POINT p1, POINT p2)   {return p1.y<p2.y ? p2:p1;}
//点积
ld dot(POINT p1, POINT p2, POINT p) {return (p.x-p1.x)*(p2.x-p1.x)+(p.y-p1.y)*(p2.y-p1.y);} //（三点式：共p1端点）
ld dot(VECTOR a, VECTOR b)      {return a.x*b.x+a.y*b.y;}   //向量式
//叉积
ld cross(POINT p1, POINT p2, POINT p)   {return (p.x-p1.x)*(p2.y-p1.y)-(p.y-p1.y)*(p2.x-p1.x);} //（三点式：共p1端点）
ld cross(VECTOR a, VECTOR b)    {return a.x*b.y-a.y*b.x;}   //向量式（aXb）
//向量长度
ld vlen(VECTOR a) {return sqrt(dot(a,a));}
//向量旋转（逆时针）
VECTOR rot(VECTOR a, ld sita)   {return {a.x*cos(sita)-a.y*sin(sita),a.x*sin(sita)+a.y*cos(sita)};}
//取单位向量
VECTOR unit(VECTOR a)   {return a/vlen(a);}
//取正交单位向量
VECTOR norm(VECTOR a)   {return VECTOR(-a.y,a.x)/vlen(a);}
//向量夹角余弦值
ld vcos(VECTOR a, VECTOR b) {return dot(a,b)/(vlen(a)*vlen(b));}
//向量夹角正弦值
ld vsin(VECTOR a, VECTOR b) {return fabs(cross(a,b))/(vlen(a)*vlen(b));}
//向量极角
//【注意】使用系统反三角函数返回nan是因为超出了定义域（大多数由于精度造成）
//【注意】故使用系统反三角函数需处理边界
ld vagl(VECTOR a, VECTOR b)
{
    ld d = dot(a,b)/(vlen(a)*vlen(b));
    if(sgn(d-1) == 0)   return 0;
    else if(sgn(d+1) == 0)  return PI;
    else    return acos(d);
}  //向量间[0,PI]
ld vagl(VECTOR a) {return atan2(a.y, a.x);}                 //单向量[-PI,PI]
 
//凸包
ll vexcnt = 0;      //凸包顶点数
POINT xy[MAXN], xyt[MAXN];     //多边形顶点存储，临时多边形顶点存储
POINT convex[MAXN]; //凸包顶点数组
 
//求凸包周长
ld convexperimeter(POINT *poly, ll n)
{
    ld ans = 0;
    for(re ll i = 1; i <= n; ++i)
    {
        ans += vlen(poly[i]-poly[i%n+1]);
    }
    return ans;
}
//计算多边形面积
ld polygonarea(POINT *poly, ll n)
{
    ld aera = 0;
    for(re ll i = 0; i < n; ++i)
    {
        aera += cross(poly[i+1], poly[(i+1)%n+1]);
    }
    return fabs(aera)/2;        //不加绝对值为有向面积
}
 
//andrew算法求凸包（凸包数组正序为逆时针）
//1.严格凸包（没有重复点和三点共线）2.非严格凸包（允许重复点和三点共线）
void andrew(ll n)
{
	vexcnt = 0;							//初始化数据
    memcpy(xyt,xy,sizeof(xy));          //备份原来顶点集
    sort(xyt+1,xyt+n+1);                //排序后xyt[1]和xyt[n]一定在凸包中
    //求解凸包顶点集
    //正向扫描（下凸包）
    convex[++vexcnt] = xyt[1];          //xyt[1]一定在凸包中
    ll j = 2;
    while(j <= n)
    {
        if(vexcnt <= 1)                 //因为xyt[2]不一定在凸包集中
        {
            convex[++vexcnt] = xyt[j++];
        }
        else
        {
            //取前面两个点
            //严格凸包：sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[j]-convex[vexcnt]))>0
            //非严格凸包：sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[j]-convex[vexcnt]))>=0
            if(sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[j]-convex[vexcnt]))>=0)  convex[++vexcnt] = xyt[j++];
            else    --vexcnt;
        }
    }
    //反向扫描（上凸包）
    //至少包含了xyt[1]和xyt[n]
    ll record = vexcnt;                 //记录下凸包的结果
    ll k = n-1;
    while(k >= 1)
    {
        if(vexcnt <= record)
        {
            convex[++vexcnt] = xyt[k--];
        }
        else
        {
            //取前面两个点
            //严格凸包：sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[k]-convex[vexcnt]))>0
            //非严格凸包：sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[k]-convex[vexcnt]))>=0
            if(sgn(cross(convex[vexcnt]-convex[vexcnt-1],xyt[k]-convex[vexcnt]))>0)  convex[++vexcnt] = xyt[k--];
            else    --vexcnt;
        }
    }
    while(convex[--vexcnt]==convex[1]);     //因为和xyt[1]相等的点都在下凸包中了
    //for(re ll i = 1; i <= vexcnt; ++i)    cout << "(" << convex[i].x << "," << convex[i].y << ")" << endl;
    return;
}
 
//直线
struct LINE
{
    POINT p;   //直线上定点
    VECTOR v;   //直线方向向量
    LINE() {}
    //点向式
    LINE(POINT _p, VECTOR _v):p(_p), v(_v) {}
    //点角式
    LINE(POINT _p, ld a):p(_p), v(VECTOR(cos(a), sin(a))) {}
    //通过参数t唯一确定直线上点坐标（点向式：P = p + t*v）
    POINT point(ld t)   {return p + t*v;}
    //平移向量r
    LINE trans(VECTOR r)    {return LINE(p+r,v);}
};
 
//有向直线
struct DIRLINE
{
    POINT p;        //定点
    VECTOR v;       //方向向量
    ld a;           //极角
    DIRLINE() {}
    DIRLINE(POINT _p, VECTOR _v):p(_p),v(_v),a(atan2(v.y,v.x)) {}
    bool operator < (const DIRLINE &DL) const    {return a < DL.a;}
};
 
//点到直线距离
ld PLdist(POINT p, LINE L) {return fabs(sin(vagl(p-L.p,L.v))*vlen(p-L.p));}
//点在有向直线左边
bool OnLeft(DIRLINE DL, POINT p) {return sgn(cross(DL.v,p-DL.p)) > 0;}
//点在有向直线右边
bool OnRight(DIRLINE DL, POINT p)   {return sgn(cross(DL.v,p-DL.p)) < 0;}
 
//两点中垂线
//返回中垂线的个数
ll PerpendicularBisector(POINT p1, POINT p2, LINE &L)
{
    if(p1 == p2)    return 0;
    L.p = (p1+p2)/2;
    L.v = rot(p2-p1, PI/2);
    return 1;
}
 
//两直线交点
POINT LLitesct;
 
//直线与直线的交点
//返回交点个数
ll LineLineIntersection(LINE L1, LINE L2, POINT &p)
{
    if(sgn(cross(L1.v, L2.v)) == 0)
    {
        if(sgn(cross(L2.p-L1.p,L2.v)) == 0)   return -1;          //两直线重合
        else    return 0;                       //两直线平行
    }
    //以L1为准
    ld t1 = -cross(L2.p-L1.p, L2.v)/cross(L2.v, L1.v);
    p = L1.p + t1*L1.v;
    //以L2为准
    //ld t2 = -cross(L1.p-L2.p, L1.v)/cross(L1.v, L2.v);
    //p = L2.p + t2*L2.v;
    return 1;
}
ll LineLineIntersection(DIRLINE DL1, DIRLINE DL2, POINT &p)
{
    if(sgn(cross(DL1.v, DL2.v)) == 0)
    {
        if(sgn(cross(DL2.p-DL1.p,DL2.v)) == 0)    return -1;          //两直线重合
        else    return 0;                       //两直线平行
    }
    //以L1为准
    ld t1 = -cross(DL2.p-DL1.p, DL2.v)/cross(DL2.v, DL1.v);
    p = DL1.p + t1*DL1.v;
    //以L2为准
    //ld t2 = -cross(L1.p-L2.p, L1.v)/cross(L1.v, L2.v);
    //p = L2.p + t2*L2.v;
    return 1;
}
 
//半平面交
//返回凸包顶点数
//【注意】若半平面交可能是无界区域，则需在外面加一个坐标很大的包围框
ll HalfPlaneIntersection(DIRLINE *DL, ll n, POINT *poly)
{
    sort(DL+1,DL+n+1);
    ll first, last;                 //双端队列的首尾元素下标
    DIRLINE *q = new DIRLINE[n+1];    //双端队列
    POINT *p = new POINT[n+1];        //p[i]为q[i]和q[i+1]的交点
    first = last = 1;
    q[1] = DL[1];                   //初始化只有一个半平面L[0]
    for(re ll i = 2; i <= n; ++i)
    {
        while(first < last && !OnLeft(DL[i], p[last-1])) --last;
        while(first < last && !OnLeft(DL[i], p[first])) ++first;
        q[++last] = DL[i];
        if(sgn(cross(q[last].v, q[last-1].v)) == 0)         //两向量平行
        {
            --last;
            if(OnLeft(q[last], DL[i].p)) q[last] = DL[i];   //同向取内测的一个
        }
        if(first < last)    LineLineIntersection(q[last-1],q[last],p[last-1]);
    }
    while(first < last && !OnLeft(q[first],p[last-1]))  --last;
    //删除无用平面
    if(last-first <= 1) return 0;                       //空集
    LineLineIntersection(q[last],q[first],p[last]);     //计算首尾两个半平面交的交点
    ll cnt = 0;
    for(re ll i = first; i <= last; ++i)    poly[++cnt] = p[i];
    return cnt;
}
 
int main()
{
    //UVALive-3890
    ios::sync_with_stdio(false);
    ll n;
    //scanf("%lld", &n);
    while(cin >> n)
    //while(~scanf("%d", &n))
    {
        if(n == 0)  break;
        POINT *p = new POINT[n+1];
        for(re ll i = 1; i <= n; ++i)
        {
            cin >> p[i].x >> p[i].y;
            //scanf("%lf%lf%lf%lf", &p1.x, &p1.y, &p2.x, &p2.y);
        }
        VECTOR *v = new VECTOR[n+1];
        VECTOR *r = new VECTOR[n+1];
        for(re ll i = 1; i <= n; ++i)
        {
            v[i] = p[i%n+1]-p[i];
            r[i] = norm(v[i]);      //单位正交向量
        }
        //二分答案
        ld left = 0, right = 20000;
        DIRLINE *DL = new DIRLINE[n+1];
        POINT *poly = new POINT[n+1];
        while(right-left > 1e-6)
        {
            ld mid = (left+right)/2;
            for(re ll i = 1; i <= n; ++i)
            {
                DL[i] = DIRLINE(p[i]+r[i]*mid,v[i]);
            }
            ll cnt = HalfPlaneIntersection(DL,n,poly);
            if(!cnt)    right = mid;
            else    left = mid;
        }
        cout << fixed << setprecision(6) << left << endl;
    }
    return 0;
}