才知道为啥我们ACM教练说计算几何是一个性价比很高的东西，因为ACM让带纸质材料啊！所以只要板子我有，那计算几何确实就变得可做了。
const db PI = acos(-1);
In int dcmp(db x) //比较两个实数大小
{
if(fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
struct Vec //向量类
{
db x, y;
In Vec operator - (const Vec& oth)const {return (Vec){x - oth.x, y - oth.y};}
In Vec operator + (const Vec& oth)const {return (Vec){x + oth.x, y + oth.y};}
In db operator ^ (const Vec& oth)const {return x * oth.x + y * oth.y;} //点积
In db operator * (const Vec& oth)const {return x * oth.y - y * oth.x;} //差积
In Vec operator * (const db& a)const {return (Vec){x * a, y * a};}
In int operator == (const Vec& oth)const {return !dcmp(x - oth.x) && !dcmp(y - oth.y);}
friend In db dis(const Vec& A) {return sqrt(A.x * A.x + A.y * A.y);} //模长
friend In Vec rot(const Vec& A, const db& a) {return (Vec){A.x * cos(a) - A.y * sin(a), A.x * sin(a) + A.y * cos(a)};} //旋转（逆时针）
In bool operator < (const Vec& oth)const {return x < oth.x || (!dcmp(x - oth.x) && y < oth.y);}
};
struct Lin //直线类
{
Vec A, v;
friend In Lin mov(const Lin& l, const db& d) //将直线沿垂直于该直线的左侧平移d个单位
{
db dv = dis(l.v);
Vec tp = (Vec){-l.v.y, l.v.x} * (1.0 / dv);
return (Lin){l.A + tp * d, l.v};
}
In Vec Point(const db& t) {return A + v * t;} //求直线上的点
};
struct Cir //圆类
{
Vec C; db r;
In Vec Point(const db& a) {return C + (Vec){cos(a) * r, sin(a) * r};}
};
In db Ang(Vec A) {return atan2(A.y, A.x);} //求向量角度
In db changeAng(db a) //将一个角转换到[0,2PI)
{
a -= PI * 2 * floor(a / (2 * PI));
return a < 0 ? a + PI * 2 : a;
}
In bool onSeg(Vec A, Vec p1, Vec p2) //A在线段p1p2上,dcmp小于等于/小于0表示含/不含端点
{
return dcmp((p1 - A) * (p2 - A)) == 0 && dcmp((p1 - A) ^ (p2 - A)) < 0;
}
In bool Cross(Vec A, Vec B, Vec C, Vec D) //判断两条线段是否相交
{
if(onSeg(A, C, D) || onSeg(B, C, D) || onSeg(C, A, B) || onSeg(D, A, B)) return 1; //加上这一句表示算端点
return dcmp((B - A) * (C - A)) * dcmp((B - A) * (D - A)) < 0 && dcmp((D - C) * (A - C)) * dcmp((D - C) * (B - C)) < 0;
}
In Vec getCross(Vec A, Vec B, Vec C, Vec D) //计算两条直线的交点
{
Vec v = B - A, w = D - C, u = A - C;
db tp = (w * u) / (v * w);
return A + v * tp;
}
In db getDisPtL(Vec P, Vec A, Vec B) //计算点P到直线AB的距离
{
db S = (B - A) * (P - A);
return fabs(S) / dis(B - A);
}
In db getLAD(Vec V) //计算直线的倾斜角（角度制）
{
db ang = atan(V.y / V.x) / PI * 180;
while(ang < 0) ang += 360;
while(dcmp(ang - 180) >= 0) ang -= 180;
return ang;
}
In bool disCC(Cir C1, Cir C2) //判断两圆是否相离（包含外切）
{
return dcmp(dis(C1.C - C2.C) - (C1.r + C2.r)) >= 0;
}
In int getCrossCL(Lin l, Cir C, vector<Vec>& ans) //求直线和圆的交点，结果储存在ans中，返回交点个数
{
db a = l.v.x, b = l.A.x - C.C.x, c = l.v.y, d = l.A.y - C.C.y;
db e = a * a + c * c, f = (a * b + c * d) * 2, g = b * b + d * d - C.r * C.r;
db del = f * f - e * g * 4;
if(dcmp(del) < 0) return 0;
if(dcmp(del) == 0) {ans.push_back(l.Point(-f / (e * 2))); return 1;}
ans.push_back(l.Point((-f - sqrt(del)) / (e * 2)));
ans.push_back(l.Point((-f + sqrt(del)) / (e * 2)));
return 2;
}
In int getCrossCC(Cir C1, Cir C2, vector<Vec>& ans) //计算两个圆的交点
{
db d = dis(C1.C - C2.C);
if(dcmp(d) == 0) return dcmp(C1.r - C2.r) ? 0 : -1;
if(dcmp(d - C1.r - C2.r) > 0 || dcmp(fabs(C1.r - C2.r) - d) > 0) return 0;
db a = Ang(C2.C - C1.C), d1 = acos((C1.r * C1.r + d * d - C2.r * C2.r) / (C1.r * d * 2));//acos(d / 2 / C1.r);
Vec p1 = C1.Point(a + d1), p2 = C1.Point(a - d1);
ans.push_back(p1); if(p1 == p2) return 1;
ans.push_back(p2); return 2;
}
In db calcS(Vec* p, int n) //计算一个多边形的面积
{
db ret = 0;
for(int i = 2; i < n; ++i)
ret += (p[i] - p[1]) * (p[i + 1] - p[1]);
return fabs(ret / 2);
}
In int PiP(Vec A, Vec* p, int n) //判定点是否在多边形内
{
int wn = 0;
p[0] = p[n];
for(int i = 1; i <= n; ++i)
{
Vec p1 = p[i - 1], p2 = p[i];
if(onSeg(A, p1, p2)) return -1;
int k = dcmp((p2 - p1) * (A - p1));
int d1 = dcmp(p1.y - A.y), d2 = dcmp(p2.y - A.y);
if(k > 0 && d1 <= 0 && d2 > 0) wn++;
if(k < 0 && d2 <= 0 && d1 > 0) wn--;
}
p[0] = (Vec){0, 0};
return wn != 0;
}
Vec S; //求凸包，返回凸包数组st和大小top.
In bool cmpP(Vec A, Vec B)
{
db s = (A - S) * (B - S);
return dcmp(s) ? s > 0 : dis(A - S) < dis(B - S);
}
In db calcP(Vec A, Vec B, Vec C) {return (B - A) * (C - A);}
In void getPol(Vec* p, int n, Vec* st, int& top)
{
int id = 1;
for(int i = 2; i <= n; ++i)
if(p[i].x < p[id].x || (!dcmp(p[i].x - p[id].x) && p[i].y < p[id].y)) id = i;
if(id ^ 1) swap(p[1], p[id]);
S = p[1];
sort(p + 2, p + n + 1, cmpP);
st[top = 1] = p[1];
for(int i = 2; i <= n; ++i)
{
while(top > 1 && calcP(st[top - 1], st[top], p[i]) < 0) top--;
st[++top] = p[i];
}
}