本文共 2052 字，大约阅读时间需要 6 分钟。
计算几何入门题
对于每个二分法中的最近点在它右边的判断问题，这是一个常见的计算几何问题。判断一个点是否在一条线段的右边，可以通过点积和叉积的方法来实现。根据叉积的正负值，我们可以判断点的位置：叉积为正表示点在顺时针方向，叉积为负则表示点在逆时针方向。
在C++中，我们需要为Point结构体重载运算符，以便于进行点积和叉积运算。点积的实现公式为x1x2 + y1y2，叉积的实现公式为x1y2 - y1x2。这些运算符对于后续的几何计算非常有用。
以下是完整的代码示例：
#include#include #include using namespace std;#define rep(i, h, t) for (int i = h; i <= t; ++i)#define dep(i, t, h) for (int i = t; i >= h; --i)#define me(x) memset(x, 0, sizeof(x))#define mid ((h + t) >> 1)#define ll long longconst int N = 1e4;int n, m, x1, y1, x2, y2, x, y, ans[N], num[N];struct Point { int x, y; Point() {} Point(int x1, int y1) { x = x1; y = y1; } Point operator+(const Point& b) const { return Point(x + b.x, y + b.y); } Point operator-(const Point& b) const { return Point(x - b.x, y - b.y); } int operator*(const Point& b) const { return x * b.x + y * b.y; } int operator^(const Point& b) const { return x * b.y - y * b.x; }};struct Line { Line() {} Point s, e; Line(Point s1, Point e1) { s = s1; e = e1; }};bool cmp(Line x, Line y) { return x.s.x < y.s.x;}int main() { freopen("1.in", "r", stdin); freopen("1.out", "w", stdout); ios::sync_with_stdio(false); while (cin >> n >> m) { rep(i, 1, n) { cin >> x >> y; l[i] = Line(Point(x, y1), Point(y, y2)); } n++; l[n] = Line(Point(x2, y1), Point(x2, y2)); sort(l + 1, l + n + 1, cmp); me(ans); me(num); while (m--) { cin >> x >> y; Point p = Point(x, y); int h = 1, t = n; while (h < t) { if (check(l[mid], p)) t = mid; else h = mid + 1; } ans[h]++; rep(i, 1, n) { if (ans[i] > 0) num[ans[i]]++; } cout << "Box" << endl; rep(i, 1, n) { if (num[i] > 0) { cout << i << ": " << num[i] << endl; } } } }}
这段代码实现了对点和线段的运算，包括点积和叉积的计算。通过对点和线段的操作符重载，我们可以方便地进行几何计算。
转载地址：http://adxfk.baihongyu.com/