板子

#define N 10000007
const int maxn = 1e6;
int prime[maxn], pcnt = 0;
bool notprime[N];
inline void prePLUS() { //挨氏筛
    notprime[1] = 1;
    for (int i = 2; i <= N; ++i) { // N以内的质数存入prime中
        if (!notprime[i]) {
            for (int j = N / i; j >= i; --j) {
                if (!notprime[j])
                    notprime[i * j] = 1;
            }
            prime[++pcnt] = i;
        }
    }
}

const int maxn = 1e6;
int prime[maxn], vis[maxn];
void Prime() {                        // 欧拉筛
    for (int i = 2; i <= maxn; i++) { // maxn以内的质数存入prime中
        if (!vis[i])
            prime[++prime[0]] = i; // prime[0]为计数
        for (int j = 1; j <= prime[0] && i * prime[j] <= maxn; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
}

const int maxn = 1e6;
int E[maxn];
void euler() { //打表求欧拉函数
    for (int i = 2; i < maxn; i++) {
        if (!E[i])
            for (int j = i; j < maxn; j += i) {
                if (!E[j])
                    E[j] = j;
                E[j] = E[j] / i * (i - 1);
            }
    }
}

const int maxn = 1e6;
bool is_prime[maxn];
int prime[maxn], phi[maxn];
void get_phi() { // 欧拉筛求素数同时求欧拉函数
    int i, j, k;
    k = 0;
    for (i = 2; i < maxn; i++) {
        if (is_prime[i] == false) {
            prime[k++] = i;
            phi[i] = i - 1;
        }
        for (j = 0; j < k && i * prime[j] < maxn; j++) {
            is_prime[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
        }
    }
}

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define mem(x, y) memset(x, y, sizeof(x))
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;

const int INF = 0x3f3f3f3f;

const double PI = acos(-1);    //圆周率
const double eps = 1e-8;       //浮点数误差值
const int maxpoint = 1e3 + 10; //最大点的个数

int sgn(double x) { //判断x是否为0
    if (fabs(x) < eps)
        return 0;
    else
        return x < 0 ? -1 : 1;
}

int Dcmp(double x, double y) { //比较两个浮点数 0相等 -1小于 1 大于
    if (fabs(x - y) < eps)
        return 0;
    else
        return x < y ? x : y;
}

//-------------------二维------平面几何----------------------------
struct Point {
    double x, y;
    Point() {}
    Point(double x, double y) : x(x), y(y) {}
    Point operator+(Point B) { return Point(x + B.x, y + B.y); }
    Point operator-(Point B) { return Point(x - B.x, y - B.y); }
    Point operator*(double k) { return Point(x * k, y * k); } //长度增加k倍
    Point operator/(double k) { return Point(x / k, y / k); } //缩短k倍
    bool operator==(Point B) { return sgn(x - B.x) == 0 && sgn(y - B.y) == 0; }
    bool operator<(Point B) { //比较两个点，用于凸包计算
        return sgn(x - B.x) < 0 || (sgn(x - B.x) == 0 && sgn(y - B.y) < 0);
    }
};
typedef Point Vector;                                            //定义向量
double Dot(Vector A, Vector B) { return A.x * B.x + A.y * B.y; } //两个向量点乘
double Len(Vector A) { return sqrt(Dot(A, A)); } //向量的长度
double Len2(Vector A) { return Dot(A, A); }      //向量的长度的平方
double angle(Vector A, Vector B) {               //向量A，B的夹角
    return acos(Dot(A, B) / Len(A) / Len(B));
}
double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; } //叉乘
double Area2(Point A, Point B, Point C) {
    return Cross(B - A, C - A); //两倍三角形面积 三角形面积S=1/2(a*b*sin<>)
}
double Distance(Point A, Point B) { return hypot(A.x - B.x, A.y - B.y); }
double Dist(Point A, Point B) {
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
Vector Normal(Vector A) { //向量A的法向量
    return Vector(-A.y / Len(A), A.x / Len(A));
}
bool Parallel(Vector A, Vector B) { //向量A,B是否平行
    return sgn(Cross(A, B)) == 0;
}
Vector Rotate(Vector A, double rad) { //将向量A逆时针旋转rad°
    return Vector(A.x * cos(rad) - A.y * sin(rad),
                  A.x * sin(rad) + A.y * cos(rad));
}
struct Line {
    Point p1, p2; //直线上的两个点
    Line() {}
    Line(Point p1, Point p2) : p1(p1), p2(p2) {}
    Line(Point p, double angle) { //根据一个点和倾斜角angle确定直线
        p1 = p;
        if (sgn(angle - PI / 2) == 0)
            p2 = (p1 + Point(0, 1));
        else
            p2 = (p1 + Point(1, tan(angle)));
    }
    Line(double a, double b, double c) {
        if (sgn(a) == 0) {
            p1 = Point(0, -c / b);
            p2 = Point(1, -c / b);
        } else if (sgn(b) == 0) {
            p1 = Point(-c / a, 0);
            p2 = Point(-c / a, 1);
        } else {
            p1 = Point(0, -c / b);
            p2 = Point(1, (-c / a) / b);
        }
    }
};
typedef Line Segment;
double Line_angle(Line v) { //返回直线得倾斜角
    // atan 的取值范围[-PI/2,PI/2]
    // atan2 的取值范围[-PI,PI]
    double k = atan2(v.p2.y - v.p1.y, v.p2.x - v.p1.x);
    if (sgn(k) < 0)
        k += PI;
    if (sgn(k - PI) == 0)
        k -= PI;
    return k;
}
int Point_line_relation(Point p, Line v) { // 直线与点的位置关系
    int c = sgn(Cross(p - v.p1, v.p2 - v.p1));
    if (c < 0) // 1:p在v的左边
        return 1;
    if (c > 0) // 2:p在v的右边
        return 2;
    return 0;
}
bool Point_on_seg(Point p, Line v) {
    return sgn(Cross(p - v.p1, v.p2 - v.p1)) == 0 &&
           sgn(Dot(p - v.p1, p - v.p2)) <= 0;
}
int Line_relation(Line v1, Line v2) { //判断两直线的位置关系
    if (sgn(Cross(v1.p2 - v1.p1, v2.p2 - v2.p2)) == 0) {
        if (Point_line_relation(v1.p1, v2) == 0)
            return 1; //重合
        else
            return 0; //平行
    }
    return 2; //相交
}
double Dis_point_line(Point p, Line v) { //点到直线的距离
    //点p1,p2,p三个点围成的面积/p1p2
    return fabs(Cross(p - v.p1, v.p2 - v.p1)) / Distance(v.p1, v.p2);
}
Point Point_line_proj(Point p, Line v) { //点在直线上的投影
    double k = Dot(v.p2 - v.p1, p - v.p1) / Len2(v.p2 - v.p1);
    return v.p1 + (v.p2 - v.p1) * k;
}
Point Point_line_symmetry(Point p, Segment v) { // 点p对直线v的对称点
    Point q = Point_line_proj(p, v);
    return Point(2 * q.x - p.x, 2 * q.y - p.y);
}
double Dis_point_sag(Point p, Segment v) { //点到线段的距离
    if (sgn(Dot(p - v.p1, v.p2 - v.p1)) < 0 ||
        sgn(Dot(p - v.p2, v.p1 - v.p2)) < 0) //点的投影不在线段上
        return min(Distance(p, v.p1), Distance(p, v.p2));
    return Dis_point_line(p, v); //点的投影在线段上
}
Point Cross_point(Point a, Point b, Point c, Point d) { //求直线ab和cd的交点
    //须先保证两直线不平行或重合
    double s1 = Cross(b - a, c - a), s2 = Cross(b - a, d - a); // ab  cd
    return Point(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
}
bool Cross_segment(Point a, Point b, Point c, Point d) { //两线段是否相交
    double c1 = Cross(b - a, c - a), c2 = Cross(b - a, d - a); // 0不相交
    double d1 = Cross(d - c, a - c), d2 = Cross(d - c, b - c); // 1相交
    return (sgn(c1) * sgn(c2)) < 0 && (sgn(d1) * sgn(d2) < 0);
    //交点是端点的时候不考虑
}

//-----------------------平面几何 多边形--------------
struct Polygon {
    int n;             //多边形的顶点数
    Point p[maxpoint]; //多边形的点
    Line v[maxpoint];  //多边形的边
};
int Point_in_polygon(Point pt, Point *p, int n) { //判断点和任意多边形的关系
    for (int i = 0; i < n; ++i)
        if (p[i] == pt)
            return 3;
    for (int i = 0; i < n; ++i) {
        Line v = Line(p[i], p[i + 1 % n]);
        if (Point_on_seg(pt, v))
            return 2;
    }
    int num = 0;
    for (int i = 0; i < n; ++i) {
        int j = (i + 1) % n;
        int c = sgn(Cross(pt - p[j], p[i] - p[j]));
        int u = sgn(p[i].y - pt.y);
        int v = sgn(p[j].y - pt.y);
        if (c > 0 && u < 0)
    }
}