牛客多校第四场 M 题题解

M Monotone Chain

M 题题意：给定平面 $nn$ 个点 $(x_i,y_i)(x\_i,y\_i)$，找到两个向量 $\mathbf{\text{a}},\mathbf{\text{b}}\backslash textbf\{a\},\backslash textbf\{b\}$ 满足 $\mathrm{\forall }1\le i\le j\le n\backslash forall\; 1\; \backslash leq\; i\; \backslash leq\; j\; \backslash leq\; n$，$({\mathbf{\text{OA}}}_i-\mathbf{\text{a}})\cdot \mathbf{\text{b}}\le ({\mathbf{\text{OA}}}_j-\mathbf{\text{a}})\cdot \mathbf{\text{b}}(\backslash textbf\{OA\}\_i-\backslash textbf\; a)\backslash cdot\; \{\backslash textbf\{b\}\}\; \backslash leq\; (\backslash textbf\{OA\}\_j-\backslash textbf\; a)\backslash cdot\; \{\backslash textbf\{b\}\}$。$n\le 1\times 10^{5}n\; \backslash leq\; 1\backslash times\; 10^5$，点范围 $\mathrm{\mid }{x}_i\mathrm{\mid },\mathrm{\mid }{y}_i\mathrm{\mid }\le 1\times 10^5|x\_i|,|y\_i|\; \backslash leq\; 1\backslash times\; 10^5$。

解法：将原式化为 ${\mathbf{\text{OA}}}_i\cdot \mathbf{\text{b}}\le {\mathbf{\text{OA}}}_j\cdot \mathbf{\text{b}}\backslash textbf\{OA\}\_i\backslash cdot\; \{\backslash textbf\{b\}\}\; \backslash leq\; \backslash textbf\{OA\}\_j\backslash cdot\; \{\backslash textbf\{b\}\}$，即是满足 ${\mathbf{\text{OA}}}_i\cdot \mathbf{\text{b}}\backslash textbf\{OA\}\_i\backslash cdot\; \{\backslash textbf\{b\}\}$ 单调递增。进一步的化简可以得到 ${\mathbf{\text{A}}}_i{\mathbf{\text{A}}}_j\cdot \mathbf{\text{b}}\le 0\backslash textbf\{A\}\_i\{\backslash textbf\{A\}\}\_j\; \backslash cdot\; \{\backslash textbf\{b\}\}\; \backslash leq\; 0$。那么问题转化为每个相邻的 $A_i{A}_{i+1}A\_iA\_\{i+1\}$ 确定了一个过原点的半个平面，问这些平面有无交点。这里可以无脑使用半平面交，但是更好的做法是使用双指针。首先对所有的不重合的 $A_i{A}_{i+1}A\_iA\_\{i+1\}$ 的射线方向进行极角排序，然后统计覆盖的射线数目，符合条件即输出当前边界的方向向量。全程可以不使用浮点数，复杂度 $\mathcal{O}(n\log n+n)\backslash mathcal\; O(n\; \backslash log\; n+n)$。

#include <bits/stdc++.h>
using namespace std;
using _T = long long; // 全局数据类型，可修改为 long long 等

constexpr _T eps = 0;
constexpr long double PI=3.1415926535897932384l;
 
// 点与向量
template<typename T> struct point
{
    T x, y;
 
    bool operator==(const point &a) const { return (abs(x - a.x) <= eps && abs(y - a.y) <= eps); }
    bool operator<(const point &a) const
    {
        if (abs(x - a.x) <= eps)
            return y < a.y - eps;
        return x < a.x - eps;
    }
    bool operator>(const point &a) const { return !(*this < a || *this == a); }
    point operator+(const point &a) const { return {x + a.x, y + a.y}; }
    point operator-(const point &a) const { return {x - a.x, y - a.y}; }
    point operator-() const { return {-x, -y}; }
    point operator*(const T k) const { return {k * x, k * y}; }
    point operator/(const T k) const { return {x / k, y / k}; }
    T operator*(const point &a) const { return x * a.x + y * a.y; } // 点积
    T operator^(const point &a) const { return x * a.y - y * a.x; } // 叉积，注意优先级
    int toleft(const point &a) const
    {
        const auto t = (*this) ^ a;
        return (t > eps) - (t < -eps);
    }                                      // to-left 测试
    T len2() const { return (*this) * (*this); }                  // 向量长度的平方
    T dis2(const point &a) const { return (a - (*this)).len2(); } // 两点距离的平方
 
    // 涉及浮点数
    long double len() const { return sqrtl(len2()); }                                                                      // 向量长度
    long double dis(const point &a) const { return sqrtl(dis2(a)); }                                                       // 两点距离
    long double ang(const point &a) const { return acosl(max(-1.0, min(1.0, ((*this) * a) / (len() * a.len())))); }        // 向量夹角
    point rot(const long double rad) const { return {x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad)}; }          // 逆时针旋转（给定角度）
    point rot(const long double cosr, const long double sinr) const { return {x * cosr - y * sinr, x * sinr + y * cosr}; } // 逆时针旋转（给定角度的正弦与余弦）
};
 
using Point=point<_T>;
 
// 极角排序
struct argcmp
{
    bool operator()(const Point &a,const Point &b) const
    {
        const auto quad=[](const Point &a)
        {
            if (a.y<-eps) return 1;
            if (a.y>eps) return 4;
            if (a.x<-eps) return 5;
            if (a.x>eps) return 3;
            return 2;
        };
        const int qa = quad(a), qb = quad(b);
        if (qa != qb)
            return qa < qb;
        const auto t = a ^ b;
        // if (abs(t)<=eps) return a*a<b*b-eps; // 不同长度的向量需要分开
        return t > eps;
    }
};

int main()
{
    int n;
    scanf("%d", &n);
    vector<Point> pt(n);
    for (int i = 0; i < n;i++)
        scanf("%lld%lld", &pt[i].x, &pt[i].y);
    vector<Point> que;
    for (int i = 1; i < n;i++)
    {
        long long x = pt[i].x - pt[i - 1].x, y = pt[i].y - pt[i - 1].y;
        if (x || y)
        {
            Point st = (Point){x, y};
            que.emplace_back(st);
        }
    }
    n = que.size();
    if (!n)
    {
        printf("YES\n0 0 1 0");
        return 0;
    }
    sort(que.begin(), que.end(), argcmp());
    for (int i = 0; i < n;i++)
        que.push_back(que[i]);
    for (int l = 0, r = 0; l < n;l++)
    {
        while (r < l + n && (que[l] ^ que[r]) >= 0)
            r++;
        if(r == l + n)
        {
            printf("YES\n0 0 %lld %lld\n", -que[l].y, que[l].x);
            return 0;
        }
    }
    printf("NO");
    return 0;
}