POJ 2318 - 玩具分配问题（计算几何叉积应用）
题目概述
给定一个矩形箱子，内部有 n 条垂直隔板将箱子分成 n+1 个区域。依次给定 m 个玩具的落点坐标，要求统计每个区域内玩具的数量。
隔板的端点坐标为 (Ui, y1) 和 (Li, y2)，其中 (x1, y1) 是矩形左上角，(x2, y2) 是矩形右下角。隔板之间不相交，且按从左到右的顺序给出。
核心思路
本题的本质是判断点与直线的位置关系。对于每个玩具，只需要判断它落在哪两个隔板之间即可。
利用叉积（Cross Product）可以判断点与直线的相对位置：
- 设直线端点为 A(x1, y1) 和 B(x2, y2)，待检测点为 P(x, y)
- 计算向量 AB × AP 的叉积值
- 若叉积 > 0，则 P 在直线 AB 的顺时针方向（左側）
- 若叉积 < 0，则 P 在直线 AB 的逆时针方向（右側）
具体实现时，将所有隔板按上端点 x 坐标排序。从左到右遍历每个玩具，对于当前玩具，依次与各隔板进行比较。当发现玩具在某隔板的左侧时，该玩具就落入该隔板左侧对应的区域。
实现代码
方案一：基础实现
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct Partition {
int upperX; // 隔板上端点 x 坐标
int lowerX; // 隔板下端点 x 坐标
};
const int MAXN = 5005;
int n, m;
int boxTopY, boxBottomY, boxLeftX, boxRightX;
int result[MAXN];
Partition partitions[MAXN];
// 计算叉积：向量 (x2-x1, y2-y1) 与 (x3-x1, y3-y1) 的叉积
long long computeCross(int x1, int y1, int x2, int y2, int x3, int y3) {
return (long long)(x2 - x1) * (y3 - y1) - (long long)(y2 - y1) * (x3 - x1);
}
// 判断点 (px, py) 是否在隔板 i 的左侧
bool isLeftOfPartition(int px, int py, const Partition& part) {
// 构建向量：隔板上端点到下端点，以及隔板上端点到玩具点
long long crossProduct = computeCross(
part.upperX, boxTopY, // 隔板上端点 A
part.lowerX, boxBottomY, // 隔板下端点 B
px, py // 玩具点 P
);
// 叉积小于 0 表示点在直线的左侧（顺时针方向）
return crossProduct < 0;
}
// 统计单个玩具所属区域
void classifyToy(int px, int py) {
for (int i = 0; i < n; i++) {
if (isLeftOfPartition(px, py, partitions[i])) {
result[i]++; // 落入第 i 个区域（第 i 条隔板左侧）
return;
}
}
result[n]++; // 落入最右侧区域（第 n+1 个区域）
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> n) {
if (n == 0) break;
cin >> m >> boxLeftX >> boxTopY >> boxRightX >> boxBottomY;
for (int i = 0; i < n; i++) {
cin >> partitions[i].upperX >> partitions[i].lowerX;
}
// 按上端点 x 坐标排序，确保隔板从左到右排列
sort(partitions, partitions + n, [](const Partition& a, const Partition& b) {
return a.upperX < b.upperX;
});
memset(result, 0, sizeof(result));
for (int i = 0; i < m; i++) {
int toyX, toyY;
cin >> toyX >> toyY;
classifyToy(toyX, toyY);
}
for (int i = 0; i <= n; i++) {
cout << i << ": " << result[i] << "\n";
}
cout << "\n";
}
return 0;
}
方案二：优化实现
#include <bits/stdc++.h>
using namespace std;
struct LineSegment {
int topX; // 上端点 x 坐标
int bottomX; // 下端点 x 坐标
bool operator<(const LineSegment& other) const {
if (topX != other.topX) return topX < other.topX;
return bottomX < other.bottomX;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
const int MAX = 5005;
int n, m;
int x1, y1, x2, y2;
bool firstCase = true;
while (cin >> n) {
if (n == 0) break;
cin >> m >> x1 >> y1 >> x2 >> y2;
vector<LineSegment> lines(n);
for (int i = 0; i < n; i++) {
cin >> lines[i].topX >> lines[i].bottomX;
}
sort(lines.begin(), lines.end());
vector<int> count(n + 1, 0);
for (int i = 0; i < m; i++) {
int px, py;
cin >> px >> py;
bool placed = false;
for (int j = 0; j < n; j++) {
// 使用叉积判断点与直线的位置关系
// (lines[j].bottomX - lines[j].topX, y2 - y1) 是隔板向量
// (px - lines[j].topX, py - y1) 是点到隔板上端点的向量
long long cross = (long long)(lines[j].bottomX - lines[j].topX) * (py - y1)
- (long long)(y2 - y1) * (px - lines[j].topX);
// 叉积大于 0 表示点在隔板左侧（顺时针方向）
if (cross > 0) {
count[j]++; // 落入第 j 个区域
placed = true;
break;
}
}
if (!placed) {
count[n]++; // 落入最右侧区域
}
}
if (!firstCase) cout << "\n";
firstCase = false;
for (int i = 0; i <= n; i++) {
cout << i << ": " << count[i] << "\n";
}
}
return 0;
}
关键细节
需要注意以下几个要点：
- 坐标系方向：题目中 y1 为上边界（较小值），y2 为下边界（较大值），与常规数学坐标系相反，需要在叉积计算时特别注意
- 排序必要性：虽然题目说明隔板已按从左到右顺序给出，但为保险起见仍进行排序
- 边界处理：题目保证玩具不会落在隔板或边界上，只需处理区域内部的归属
该算法的时间复杂度为 O(n × m)，空间复杂度为 O(n)，完全能够满足题目约束（n, m ≤ 5000）。
