跟我一起，成为计算几何霸王吧！
2026-07-28 09:48:54
发布于：广东
@Asdfre 教我
向量
https://book.pep.com.cn/1421001122191/mobile/index.html 第六章。
向量就是反映一个东西（如物理中的力、速度等）方向和大小的量。以 表示。它的大小为模长 。
显然，在 维空间内，存在 个向量，以它们作为基底，则所有向量都可以用它们表示。这个其实也很好找，取平行于每一维的任意向量各一个即可。为方便表示，每个基底向量都取模长为 的。
这样，我们就可以用坐标 表示一个 维向量 了。
（写法不太严谨，看得懂就行）
定义向量的模长为一个数值 。
定义向量的加运算为一个向量 ，显然符合交换律、结合律。
定义向量的数乘运算为一个向量 ，显然也符合交换律、结合律，加和数乘也符合分配律。
欸求和能这么写吗，不管了。
这些应该很容易理解吧。
我们看到 维向量。
定义向量 的点乘为一个数值 。如果 ，则 与 垂直。
定义向量 的叉乘……二维空间下二维向量没有叉乘，但是三维下有，为一个向量 。
但是，我们可以把二维空间变成三维空间，将 变为 。这样，这两个向量的叉乘就为 了。我们取第三维 。
这个有啥用呢？注意到，这个的绝对值刚好是两个向量移到原点围成的平行四边形的面积；如果 ，则 在 的逆时针方向；如果 ，则 在 的顺时针方向；如果 ，则 与 平行。
然后，注意到，嗯，所有计算几何问题都是向量问题。这咋注意到的（（（
尝试 解决以下问题。
判断两线段的公共点数量（0、1、无数）
取两线段端点，分别用叉积判断是否另外一条线段两个端点在这条线段同一侧。如果两条线段都在异侧，则说明有恰好 个公共点；如果存在一条线段在同侧且叉积 ，则说明没有公共点；否则说明两条线段共线。分类讨论一下位置即可。
计算两平行直线的距离
任意取 一个点， 两个点，用叉积计算三个点围成的平行四边形的面积，除以 上两个点的长即可。
计算两相交直线的交点
每条线段任取两个点。
显然 。
然后通过往 CD 方向偏移即可找到 E。
异侧显然一样。
其实这些都是基础（（（
代码中，我们应避免精度误差，能不用浮点就不用浮点。
HDU1756
给定一个多边形（不一定是凸多边形），问一个点是否在它内部。
我们可以以这个点为端点，引出一条射线（为方便实现，可以用一个长度特别长的线段代替），判断这个多边形与射线有几个交点，奇数个在里面，偶数个在外面。
但是注意到如果射线与多边形有交点刚好在顶点，这个特别难讨论。所以我们需要尽量不要让射线与多边形交点为顶点。我设计的“射线”为 ，斜率为 ，在 足够大的情况下不可能有 以外在数据范围下的整点，规避了这个问题。
注意要特判查询的点在边上 / 点上的情况，但这个数据好像没卡/咦
注意到代码中使用了 0 个浮点运算，大大滴好。
namespace cjdst{
class Vec{
public:
ll x, y;
Vec(){
x = y = 0;
}
Vec(ll xx, ll yy){
x = xx, y = yy;
}
ll operator * (const Vec b) const{
return (x * b.x) + (y * b.y);
}
ll operator ^ (const Vec b) const{
return (x * b.y) - (y * b.x);
}
Vec operator - (const Vec b) const{
return Vec(x - b.x, y - b.y);
}
};
typedef Vec Point;
const int INF = 20260727;
int sign(ll val){
return (val < 0 ? -1 : val == 0 ? 0 : 1);
}
bool on_edge(Point x, Point y, Point p){
return (((x - y) ^ (x - p)) == 0);
}
bool banana(Point x1, Point y1, Point x2, Point y2){
auto c1 = (y1 - x1) ^ (x2 - x1);
auto c2 = (y1 - x1) ^ (y2 - x1);
auto c3 = (y2 - x2) ^ (x1 - x2);
auto c4 = (y2 - x2) ^ (y1 - x2);
return (sign(c1) * sign(c2) <= 0 && sign(c3) * sign(c4) <= 0);
}
bool solve(){
int n;
if(!(std::cin >> n)) return 0;
std::vector <Point> a(n + 5);
for(int i = 1; i <= n; i++){
int x, y;
std::cin >> x >> y;
a[i] = Point(x, y);
}
int m;
std::cin >> m;
while(m--){
int x, y;
std::cin >> x >> y;
Point p(x, y), q(x + INF, y + INF + 1);
int cur = 0;
for(int i = 1; i <= n; i++){
if(on_edge(a[i], a[i % n + 1], p)){
cur = 1;
break;
}
if(banana(a[i], a[i % n + 1], p, q)) cur ^= 1;
}
std::cout << (cur ? "Yes\n" : "No\n");
}
return 1;
}
}
时间复杂度：。
P2742
给定 个点，求它们构成的凸包。
G 开头神秘算法。
首先选 最小的点，如果有多个，选 最小 / 最大的点。显然该点为凸包顶点之一。为方便表示，我称它为“最小点”。
然后将其它点按照与这个点的方向排序。这里选逆时针方向。
然后用一个类似单调栈的东西，记录下当前凸包每一条线。
经过一个点时，如果它在当前凸包外面，就一直弹栈，直到到凸包里面，然后凸包点连向它。
namespace cjdst{
class Vec{
public:
ll x, y;
Vec(){
x = y = 0;
}
Vec(ll xx, ll yy){
x = xx, y = yy;
}
ll operator * (const Vec b) const{
return (x * b.x) + (y * b.y);
}
ll operator ^ (const Vec b) const{
return (x * b.y) - (y * b.x);
}
Vec operator - (const Vec b) const{
return Vec(x - b.x, y - b.y);
}
};
typedef Vec Point;
void solve(){
int n;
std::cin >> n;
std::vector <Point> a(n + 5);
double mn = 0x3f3f3f3f, mx = 0;
for(int i = 1; i <= n; i++){
double x, y;
std::cin >> x >> y;
mx = std::max(mx, y);
mn = std::min(mn, y);
a[i] = Point(std::round(x * 100), std::round(y * 100));
}
std::swap(a[std::min_element(a.begin() + 1, a.begin() + n + 1, [](Point x, Point y) -> bool{
if(x.x != y.x) return x.x < y.x;
return x.y < y.y;
}) - a.begin()], a[1]);
std::sort(a.begin() + 2, a.begin() + n + 1, [&](Point x, Point y) -> bool{
Vec l1 = x - a[1], l2 = y - a[1];
if((l1 ^ l2) != 0) return ((l1 ^ l2) > 0);
return ((l1 * l1) < (l2 * l2));
});
std::vector <Point> ans{a[1], a[2]};
auto check = [&](Point cur){
Point x = ans[ans.size() - 2], y = ans[ans.size() - 1];
Vec l1 = y - x, l2 = cur - x;
return ((l1 ^ l2) <= 0);
};
for(int i = 3; i <= n; i++){
while(ans.size() > 1 && check(a[i])) ans.pop_back();
ans.push_back(a[i]);
}
long double ans2 = 0;
for(int i = 0; i < ans.size(); i++){
ans2 += sqrtl((ans[i] - ans[(i + 1) % ans.size()]) * (ans[i] - ans[(i + 1) % ans.size()]));
}
std::cout << std::setprecision(2) << std::fixed << ans2 / 100 << '\n';
}
}
时间复杂度：。
CF166B
给定一个凸多边形和一个任意多边形，问是否在凸多边形内。
显然多边形在凸边形内可以转化成每个顶点都在凸多边形内，也就是说其实是 次查询点是否在凸多边形内。
显然如果是任意多边形很难做到优于 的做法，但是这是一个凸多边形。
一种做法是将 个点加入原来的凸多边形跑一遍凸包，判断新凸包是否与原凸包相同，是 的，但是我们希望在线解决。
UPD：在上一题中补充了最小点的定义（其实是我瞎编的定义），去看一下。
我们可以和处理凸包差不多的方法，计算它与凸多边形的最小点的相对方向，二分出原凸多边形这个方向的前驱和后驱两个点，判断它是否在这个直线外面即可。
如图所示，G 在 BC 的外面，所以它在凸包的外面。
注意有一个 corner case：这个点的可能与最小点和另一个点三点共线，如果最小点恰好与这个点有连边会出问题，需要特判。
由于逆时针好看，所以我这里倒序输入，顺时针转逆时针了。
namespace cjdst{
// Vec, Point
void solve(){
int n;
std::cin >> n;
std::vector <Point> a(n + 5);
for(int i = n; i; i--){
int x, y;
std::cin >> x >> y;
a[i] = Point(x, y);
}
int idx = std::min_element(a.begin() + 1, a.begin() + n + 1, [](Point &x, Point &y){
if(x.x != y.x) return x.x < y.x;
return x.y < y.y;
}) - a.begin();
auto b = a;
for(int i = 1; i <= n; i++){
a[i] = b[(i + idx - 2) % n + 1];
}
int m;
std::cin >> m;
bool flag = 1;
while(m--){
int x, y;
std::cin >> x >> y;
Point p(x, y);
auto cmp = [&](Point x, Point y) -> bool{
Vec l1 = x - a[1], l2 = y - a[1];
return ((l1 ^ l2) > 0);
};
int idx = std::upper_bound(a.begin() + 1, a.begin() + n + 1, p, cmp) - a.begin() - 1;
if(!cmp(p, a[idx]) && !cmp(a[idx], p) && idx == 2){// 特判！
flag = 0;
continue;
}
Vec l1 = a[idx % n + 1] - a[idx], l2 = p - a[idx];
if((l1 ^ l2) <= 0) flag = 0;
}
std::cout << (flag ? "YES\n" : "NO\n");
}
}
时间复杂度：。
有帮助，赞一个