求解计算几何中的二维半平面交问题
#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;
}