半平面交问题

2024-08-14

求解计算几何中的二维半平面交问题

#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
using namespace std;
const double EPS = 1e-8;
const double INF = 1e12;
int sgn(double x)
{
    if (fabs(x) < EPS)
        return 0;
    else
        return x < 0 ? -1 : 1;
}
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); }
};
typedef Point Vector;
double Cross(Vector A, Vector B) { return A.x * B.y - A.y * B.x; }
struct Line
{
    Point p;
    Vector v;
    double ang;
    Line() {};
    Line(Point p, Vector v) : p(p), v(v) { ang = atan2(v.y, v.x); }
    friend bool operator<(Line a, Line b) { return a.ang < b.ang; }
};
bool OnLeft(Line L, Point p) { return sgn(Cross(L.v, p - L.p)) > 0; }
Point Cross_point(Line a, Line b)
{
    Vector u = a.p - b.p;
    double t = Cross(b.v, u) / Cross(a.v, b.v);
    return a.p + a.v * t;
}
vector<Point> HPI(vector<Line> L)
{
    int n = L.size();
    sort(L.begin(), L.end());
    int first, last;
    vector<Point> p(n);
    vector<Line> q(n);
    vector<Point> ans;
    q[first = last = 0] = L[0];
    for (int i = 1; i < n; i++)
    {
        while (first < last && !OnLeft(L[i], p[last - 1]))
            last--;
        while (first < last && !OnLeft(L[i], p[first]))
            first++;
        q[++last] = L[i];
        if (fabs(Cross(q[last].v, q[last - 1].v)) < EPS)
        {
            last--;
            if (OnLeft(q[last], L[i].p))
                q[last] = L[i];
        }
        if (first < last)
            p[last - 1] = Cross_point(q[last - 1], q[last]);
    }
    while (first < last && !OnLeft(q[first], p[last - 1]))
        last--;
    if (last - first <= 1)
        return ans;
    p[last] = Cross_point(q[last], q[first]);
    for (int i = first; i <= last; i++)
        ans.push_back(p[i]);
    return ans;
}
int main()
{
    int T, n;
    cin >> T;
    while (T--)
    {
        cin >> n;
        vector<Line> L;
        L.push_back(Line(Point(0, INF), Vector(-1, 0)));
        L.push_back(Line(Point(0, 0), Vector(0, -1)));
        while (n--)
        {
            double a, b;
            scanf("%lf%lf", &a, &b);
            L.push_back(Line(Point(0, a), Vector(1, b)));
        }
        vector<Point> ans = HPI(L);
        printf("%d\n", ans.size() - 2);
    }
    return 0;
}