【计算几何】向量

要么使用atan2的long double类型，要么使用整数。

无误差版本的极角排序。

int n;

struct Vector {
    ll x;
    ll y;
    int id;
    Vector() {}
    Vector(ll _x, ll _y) {
        x = _x, y = _y;
    }
    bool top() const {
        return y < 0 || y == 0 && x < 0;
    }
} vec[100005];

ll dot(const Vector &v1, const Vector &v2) {
    return v1.x * v2.x + v1.y * v2.y;
}

ll cross(const Vector &v1, const Vector &v2) {
    return v1.x * v2.y - v1.y * v2.x;
}

bool polarLess(const Vector &v1, const Vector &v2) {
    bool top1 = v1.top(), top2 = v2.top();
    if(top1 != top2)
        return top1;
    return cross(v1, v2) > 0;
}

bool angleLess(const Vector &v1, const Vector &v2, const Vector &v3, const Vector &v4) {
    Vector res12(dot(v1, v2), abs(cross(v1, v2)));
    Vector res34(dot(v3, v4), abs(cross(v3, v4)));
    return cross(res12, res34) > 0;
}

    struct Vector {
        double x, y;
        Vector() {}
        Vector(double x, double y): x(x), y(y) {}
        double length() {
            return sqrt(x * x + y * y);
        }
        Vector operator+(const Vector& v)const {
            return Vector(x + v.x, y + v.y);
        }
        Vector operator-(const Vector& v)const {
            return Vector(x - v.x, y - v.y);
        }
        Vector operator*(const double& k)const {
            return Vector(k * x, k * y);
        }
        Vector operator/(const double& k)const {
            return Vector(x / k, y / k);
        }
        Vector rotate(double k) {
            k = PI / 180 * k;
            return Vector(x * cos(k) - y * sin(k), x * sin(k) + y * cos(k));
        }
        void show() {
            printf("%.12f %.12f
", x, y);
        }
    };

若极角排序的中心是凸包边界上的点（也就是说其他点都在这个点的同一侧），那么可以使用叉积来极角排序。

Vector baseV;

bool polarLess2(const Vector &v1, const Vector &v2) {
    return cross(v1 - baseV, v2 - baseV) < 0;
}

两个点围绕极角中心baseV形成的三角形的有向面积，指示了（旋转一个劣角时）两个点谁在谁的右侧。