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;
}
