几何点集与线段检测解题思路

核心功能

1. 计算给定二维点集的凸包（Convex Hull）
2. 判断给定线段是否与凸包相交（BAD）或完全在凸包外部（GOOD）

实现步骤

一、凸包计算阶段

1. 点集预处理：

   • 读取所有二维点坐标
   • 按x坐标排序（x相同则按y排序）

2. Andrew算法构建凸包：

   • 正向扫描构建上凸包
   • 反向扫描构建下凸包
   • 最终得到逆时针排列的凸包顶点序列

3. 计算边角度：

   • 对每条凸包边计算其与x轴的夹角（-π/2到3π/2范围）
   • 存储为角度数组用于后续查询

二、线段检测阶段

1. 线段方向分析：

   • 计算线段方向向量与x轴的夹角
   • 使用二分查找在凸包角度数组中定位最近边

2. 位置关系判断：

   • 找到线段两个端点对应的凸包切线点
   • 通过叉积判断线段是否与凸包相交：
     • 若两端点都在凸包同一侧 → GOOD（不相交）
     • 否则 → BAD（相交）

关键算法

1. 凸包构建：

   • 时间复杂度：O(nlogn)（主要来自排序）
   • 空间复杂度：O(n)

2. 线段检测：

   • 单次查询时间复杂度：O(logn)（二分查找）
   • 基于叉积的位置判断保证几何正确性

技术亮点

1. 数值稳定性处理：

   • 自定义add函数处理浮点精度问题
   • 角度归一化到[-π/2, 3π/2]区间

2. 高效查询设计：

   • 预计算凸包边角度
   • 二分查找快速定位

3. 几何运算封装：

   • 点类重载运算符简化向量运算
   • 封装点积、叉积等基本操作

输出说明

• "GOOD"：线段完全在凸包外部
• "BAD"：线段与凸包相交或在其内部

该实现适用于需要快速判断线段与凸包位置关系的场景，如碰撞检测、几何查询等应用。

#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

const double Pi = acos(-1.0);
const double EPS = 1e-10;
const int MAX_N = 100088;

double add(double a, double b);

struct P
{
    double x;
    double y;
    P()
    {
    }
    P(double x, double y) : x(x), y(y)
    {
    }
    bool operator<(const P &ri) const
    {
        return x < ri.x || x == ri.x && y < ri.y;
    }
    P operator+(const P &ri) const
    {
        return P(x + ri.x, y + ri.y);
    }
    P operator-(const P &ri) const
    {
        return P(x - ri.x, y - ri.y);
    }
    P operator*(double d) const
    {
        return P(x * d, y * d);
    }
    double dot(const P &ri) const
    {
        return add(x * ri.x, y * ri.y);
    }
    double det(const P &ri) const
    {
        return add(x * ri.y, -y * ri.x);
    }
    double angel() const
    {
        double tmp = atan2(y, x);
        if (tmp < -Pi / 2)
        {
            tmp += 2 * Pi;
        }
        return tmp;
    }
} ps[MAX_N], qs[MAX_N];

double angles[MAX_N];
int convex_hull(int n);

int main()
{
    P p1, p2;
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%lf%lf", &ps[i].x, &ps[i].y);
    }
    if (N < 2)
    {
        while (~scanf("%lf%lf%lf%lf", &p1.x, &p1.y, &p2.x, &p2.y))
        {
            printf("GOOD\n");
        }
    }
    int h = convex_hull(N);

    for (int i = 0; i < h; i++)
    {
        angles[i] = (qs[i + 1] - qs[i]).angel();
    }

    while (~scanf("%lf%lf%lf%lf", &p1.x, &p1.y, &p2.x, &p2.y))
    {
        const P &t1 = qs[(upper_bound(angles, angles + h, (p2 - p1).angel()) - angles) % h];
        const P &t2 = qs[(upper_bound(angles, angles + h, (p1 - p2).angel()) - angles) % h];
        printf((t1 - p1).det(t1 - p2) * (t2 - p1).det(t2 - p2) >= 0 ? "GOOD\n" : "BAD\n");
    }
    return 0;
}

inline double add(double a, double b)
{
    if (fabs(a + b) > (fabs(a) + fabs(b)) * EPS)
    {
        return a + b;
    }
    return 0.0;
}

int convex_hull(int n)
{
    int k = 0;
    sort(ps, ps + n);
    for (int i = 0; i < n; i++)
    {
        while (k > 1)
        {
            if ((qs[k - 1] - qs[k - 2]).det(ps[i] - qs[k - 1]) <= 0)
            {
                --k;
            }
            else
            {
                break;
            }
        }
        qs[k++] = ps[i];
    }
    int t = k;
    for (int i = n - 2; i >= 0; i--)
    {
        while (k > t)
        {
            if ((qs[k - 1] - qs[k - 2]).det(ps[i] - qs[k - 1]) <= 0)
            {
                --k;
            }
            else
            {
                break;
            }
        }
        qs[k++] = ps[i];
    }
    return k - 1;
}