计算几何

Asdfre

2026-08-03 21:34:52

发布于：广东

98阅读

0回复

0点赞

基础知识

（本篇以简短的语言只讲代码中常用的，如果后面做题有新的自然会补，想深入了解？）。

前置：1.向量是可以用一个坐标表示的。
2.向量减： $\vec a$ $-$ $\vec b$ $=$ $(x_a-x_b，y_a-y_b)$ 。
3.向量数乘： $\vec a$ $*$ $k$ $=(x_a*k，y_a*k)$ $k \in R$ 。
4.向量模长： $| \overrightarrow {AB} |$ $=$ $dis(AB)$ 。

考虑一个有方向有大小的 $\vec a$ ，有两个点 $A(x1，y1)$ ， $B(x2，y2)$ 固定这个向量，方向 $A$ 到 $B$ ，在代码里我们用 $B-A$ 表示 $\vec a$ 。

（注：夹角为 $\theta$ ）
考虑点乘 $\vec a$ $\cdot$ $\vec b$ $=$ $|a|$ $*$ $|b|$ $*$ $cos \theta$ ，代表 $\vec a$ 在 $\vec b$ 上的投影长度再乘上 $| \vec b |$ 。
坐标表示： $dot(\vec a，\vec b)$ $=$ $x_a*x_b+y_a*y_b$ 。

考虑叉乘 $\vec a$ $\times$ $\vec b$ $=$ $| \vec a |$ $*$ $| \vec b |$ $*$ $sin \theta$ 表示以 $\vec a$ ， $\vec b$ 为底边的平行四边形面积
~~（看了那么多图应该可以自己画了吧？）~~
坐标表示： $cross(\vec a，\vec b)$ $=$ $x_a*y_b-y_a*x_b$ 。

还有很多点，线的关系（我们暂且不考虑三维，反正我不会），需要向某位大佬自学再食用。

应用专题

一个点是否在任意多边形内：

数学上我们取一条与所有多边形边不平行的射线，这个射线从这个点出发与多边形相交的边数，奇内偶外
代码中我们取一个 $+\infty，+\infty$ 的点（通常可以为 $10^9$ ）与这个点构成一个线段，再用线段是否相交的方法解决就行。当然有 $\frac {1}{10^9}$ 的概率会导致挂掉（可以想一想为什么？），但概率极小一般不会错。

例题：HDU-1756 Cupid's Arrow

#include<iostream>
#include<vector>
using namespace std;
namespace CZW{
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll=long long;
	using ull=unsigned long long;
	using i128=__int128;
	constexpr ll inf=1e9;
	struct V{
		ll x,y;
		V (ll _x=0,ll _y=0) : x(_x),y(_y) {}
	};
	V operator-(const V& a1,const V& a2){
		return {a1.x-a2.x,a1.y-a2.y};
	}
	ll dot(const V& a1,const V& a2){
		return a1.x*a2.x+a1.y*a2.y;
	}
	ll cross(const V& a1,const V& a2){
		return a1.x*a2.y-a1.y*a2.x;
	}
	ll area(const V& a,const V& b,const V& c){
		return cross(b-a,c-a);
	}
	ll sign(const ll& x){
		if (x<0) return -1;
		else if (x==0) return 0;
		else return 1;
	}
	void Main(){
		int n;
		auto get=[&](int idx)->int{
			return idx>=n?1:idx+1;
		};
		while(cin>>n){
			vec<V> a(n+1);
			for (int i=1;i<=n;++i) cin>>a[i].x>>a[i].y;
			V o={inf,inf-13};
			int m; cin>>m;
			for (int i=1;i<=m;++i){
				V g; cin>>g.x>>g.y;
				bool on=false;
				for (int j=1;j<=n;++j){
					if (cross(g-a[j],g-a[get(j)])==0&&dot(g-a[j],g-a[get(j)])<=0){
						on=true;
						break;
					}
				}
				if (on) {
					cout<<"Yes"<<endl;
					continue;
				}
				int c=0;
				V u=o-g;
				for (int j=1;j<=n;++j){
					V v=a[get(j)]-a[j];
					V v1=a[j]-g,v2=a[get(j)]-g;
					V w1=o-a[j],w2=g-a[j];
					if (sign(cross(u,v1))*sign(cross(u,v2))<=0&&sign(cross(v,w1))*sign(cross(v,w2))<=0){
						++c;
					}
				}
				if (c&1) cout<<"Yes"<<endl;
				else cout<<"No"<<endl;
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int Test=1;
//	cin>>Test;
	while(Test--) CZW::Main();
	return 0;
}

障碍物最短距离问题

考虑在一个二维平面上有两个点 $A$ ， $B$ ，有一个圆，问两点之间不经过圆的最短距离。
如图：

如 $A$ ， $B$ ，当最短距离不经过圆时则直接输出答案；
再考虑 $C$ ， $D$ 情况，显然找切点再走一段劣弧是最短距离
$Ans=min(CF+\overset{\frown}{FG}+GD，CH+\overset{\frown}{HI}+DI)$

例题：Interstellar … Fantasy Gym - 102056F

乍一看是三维问题，但是我们注意到 $A$ ， $B$ 与圆心 $O$ 三点构成一个平面，可以转化为二维来做。

当然一些角度问题得仔细思考

#include<bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll=long long;
	using ull=unsigned long long;
	using lb=long double;
	using i128=__int128;
	lb pw(const lb& a) {
		return a*a;
	}
	struct V {
		lb x,y,z;
		V (lb _x=0,lb _y=0,lb _z=0) : x(_x),y(_y),z(_z) {}
	};
	lb dist(const V& a,const V& b) {
		return sqrtl(pw(a.x-b.x)+pw(a.y-b.y)+pw(a.z-b.z));
	}
	lb Acos(const lb& v) {
		return acosl(max((lb)-1,min((lb)1.0,v)));
	}
	void Main() {
		V o,s,t;
		lb r;
		cin>>o.x>>o.y>>o.z>>r;
		cin>>s.x>>s.y>>s.z>>t.x>>t.y>>t.z;
		lb so=dist(s,o),to=dist(t,o),st=dist(s,t);
		if (st==0) {
			cout<<fixed<<setprecision(10)<<0<<endl;
			return ;
		}
		lb p=(so+to+st)/2.0;
		lb h=2.0*sqrtl(max((lb)0,p*(p-so)*(p-st)*(p-to)))/st;
		bool is1=pw(so)+pw(st)>pw(to),is2=pw(to)+pw(st)>pw(so);
		if (is1&&is2&&h<r) {
			lb j1=Acos((pw(so)+pw(to)-pw(st))/(2.0*to*so));
			lb len1=sqrtl(max((lb)0,pw(so)-pw(r))),len2=sqrtl(max((lb)0,pw(to)-pw(r)));
			lb j2=Acos(r/so),j3=Acos(r/to);
			lb j4=j1-j2-j3;
			cout<<fixed<<setprecision(10)<<len1+len2+r*j4<<endl;
		} else cout<<fixed<<setprecision(10)<<st<<endl;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int Test=1;
	cin>>Test;
	while(Test--) CZW::Main();
	return 0;
}

Interested in Skiing

一道非常神秘综合的计算几何，思维含量还是蛮高的。

对于这么一道题，直接看 Kotori 是否能穿过会非常复杂，但是我们可以换一个角度看问题：障碍物将 Kotori 拦住的小代价是什么？我们成为了拦截 Kotori 的人。

什么时候障碍物会将 Kotori 拦住？相当于左边界（定义为 $0$ 节点）和右边界（定义为 $n+1$ 节点）是连通的。

换句话说，我们（你也可以认为障碍物们）可以定义代价 $w_{i,j}$ 为在 $i$ 障碍物与 $j$ 障碍物（把它们看做 $i$ 和 $j$ 节点）连一条边，那么根据木桶原理，拦截能力取决于最小的地方，而障碍物会让这个值尽可能大，穿过这个 $n$ 个节点的答案是个最大的最小路径，这个我们可以用一个 Dijsktra 解决，在所有路径中让其中最小值尽可能大！

上面的有点绕，细细评鉴一下。

这样我们把二维平面问题转化为图论，接着就是考虑代价。

根据题目要求的，代价 $w_{i,j}$ 就是只考虑穿过 $i$ 和 $j$ 节点所需的最大 $v_x$ ，因为要。考虑到我们可以枚举端点（因为极限情况下端点一定取到最小），接着按题意计算即可：

$w_{i,j}= \frac {\Delta x}{t_{通过}}=\frac{\Delta x}{\frac {\Delta y}{v_y}}=v_y \times \frac {\Delta x}{\Delta y}$

但我们要考虑特殊情况：

绝对的死路：两个障碍物 $y$ 有交集，但本该在左边的障碍物其 $x$ 值大于右侧，说明被严格封死，代价 $+ \infty$ 。
枚举端点时，若 $y$ 相等则无意义跳过。
如果 $y1\not =y2$ ，那么如果 $x1<x2$ ，则中间有空隙，可以直接穿过去，所以代价中应该是 $\max (0,\Delta x)$ 。

这样我们就做完了：

#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	constexpr double inf = 1e9;
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	struct Node {
		int x1, y1, x2, y2;
		Node (int _1 = 0, int _2 = 0, int _3 = 0, int _4 = 0) : x1(_1), y1(_2), x2(_3), y2(_4) {}
	};
	void Main() {
		int n, m, v;
		cin >> n >> m >> v;
		vec<Node> a(n + 1);
		for (int i = 1; i <= n; ++i) cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
		auto get = [&](const Node & x, const Node & y)->double{//两个障碍物最大代价
			double mi = max(min(x.y1, x.y2), min(y.y1, y.y2));
			double ma = min(max(x.y1, x.y2), max(y.y1, y.y2));
			if (mi <= ma) {
				double mid = (mi + ma) / 2.0;
				auto get_x = [&](const Node & aa, double y, bool is)->double{
					if (aa.y1 == aa.y2) return is ? max(aa.x1, aa.x2) : min(aa.x1, aa.x2);
					return aa.x1 + (aa.x2 - aa.x1) * (y - aa.y1) / (double)(aa.y2 - aa.y1);
				};
				if (get_x(x, mid, true) - get_x(y, mid, false) >= 1e-8) return inf;
			}
			ma = 0;
			vec<pair<int, int>> p1 = {{x.x1, x.y1}, {x.x2, x.y2}}, p2 = {{y.x1, y.y1}, {y.x2, y.y2}};
			for (auto [x1, y1] : p1) {
				for (auto [x2, y2] : p2) {
					if (y1 != y2) {
						ma = max(ma, (double)v * max(0, x1 - x2) / abs(y1 - y2));
					}
				}
			}
			return ma;
		};
		vec<double> dis(n + 2, -1.0);
		dis[0] = inf;
		priority_queue<pair<double, int>> q;
		q.emplace(inf, 0);
		while (!q.empty()) {
			auto [d, u] = q.top();
			q.pop();
			if (d < dis[u]) continue;
			if (u == n + 1) break;
			for (int nxt = 1; nxt <= n + 1; ++nxt) {
				if (u == nxt) continue;
				double w = 0;
				if (u == 0 && nxt == n + 1) w = 0;
				else if (!u) {
					w = min(a[nxt].x1, a[nxt].x2) == -m ? inf : 0;
				} else if (nxt == n + 1) {
					w = max(a[u].x1, a[u].x2) == m ? inf : 0;
				} else {
					w = get(a[u], a[nxt]);//获取连接的最大价值
				}
				double nd = min(d, w);//当前答案取决于这段路中最小的一个
				if (nd > dis[nxt]) {
					dis[nxt] = nd;
					q.emplace(nd, nxt);
				}
			}
		}
		if (dis[n + 1] >= inf / 2) cout << -1 << endl;
		else cout << fixed << setprecision(10) << dis[n + 1];
	}
}
int main() {
	CZW::init();
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

感觉非常巧妙！！

凸包专题

经典问题：考虑任意几个点，求最小凸包。

一般我们用的是 $Andrew$ 算法，按照 $x，y$ 排序，以便我们向量处理。

接着用一个栈去存处理的节点，当新加入一个节点时，考虑栈顶上两个点是否与这个点构成凸包，如果可以就入栈反之弹出栈顶，直到能构成。

（如图，当前处理完 $k$ 个节点，考虑加入第 $k+1$ 个节点）

若 $\overrightarrow {(k-1)k}$ $\times$ $\overrightarrow{(k-1)(k+1)}$ $\le 0$ 则不合法，
反之合法

特别的，等于0时一定要弹出，因为这个点是在凸包上而不是顶点

实现部分我个人比较喜欢分上凸壳，下凸壳处理。

代码（以模板题求周长为例子）

#include<bits/stdc++.h>
using namespace std;
namespace CZW{
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll=long long;
	using lb=long double;
	using ull=unsigned long long;
	using i128=__int128;
	constexpr lb eps=1e-9;
	struct V{
		lb x,y;
		V(lb _x=0,lb _y=0) :x(_x),y(_y) { }
		bool operator<(const V& other){
			return fabs(x-other.x)>eps?x<other.x:y<other.y;
		}
	};
	V operator-(const V& a,const V& b){
		return {a.x-b.x,a.y-b.y};
	}
	lb cross(const V& a,const V& b){
		return a.x*b.y-a.y*b.x;
	}
	lb dist(const V& a,const V& b){
		return sqrtl((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
	}
	void Main(){
		int n; cin>>n;
		vec<V> a(n+1);
		for (int i=1;i<=n;++i) cin>>a[i].x>>a[i].y;
		sort(a.begin()+1,a.end());
		vec<V> stk((n<<1)+5,0);
		int k=0;
		for (int i=1;i<=n;++i){
			while(k>=2&&cross(stk[k-1]-stk[k],a[i]-stk[k-1])<=0) --k;
			stk[++k]=a[i];
		}
		int t=k+1;
		for (int i=n-1;i>=1;--i){
			while(k>=t&&cross(stk[k-1]-stk[k],a[i]-stk[k-1])<=0) --k;
			stk[++k]=a[i];
		}
		--k;
//		for (int i=1;i<=k;++i) cout<<stk[i].x<<stk[i].y<< ' ';
//		cout<<endl;
		lb ans=0;
		for (int i=1;i<=k;++i){
			ans+=dist(stk[i],stk[(i%k)+1]);
		}
		cout<<fixed<<setprecision(2)<<ans;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int Test=1;
	//cin>>Test;
	while(Test--) CZW::Main();
	return 0;
}

时间复杂度 $O(n \log n)$

考虑进阶问题：如何快速求一个点 $S$ 是否在凸包内

subtask1： $O(n)$ ，显然是简单的，对于每条线段和这个点判断一下位置，如果都在同侧则在内部

subtask2： $O(\log n)$ ，考虑固定一个凸包顶点，我习惯固定 $x$ 最小， $y$ 最小的点，记为 $X$ ，对其他点按照与 $X$ 的极角从小到大排序（若极角相等则按照与X距离从小到大）。

当然这种方法也是求凸包的一种（ $Gramham$ ），判断条件也是一样的，待会补。

回归正题，这么做完之后，再对 $S$ 与 $X$ 求一遍极角。

结合图

考虑二分，最后会缩小到只包含一个线段的区间

若 $\overrightarrow {u}$ $\times$ $\overrightarrow{ls}$ $\ge 0$ 则合法，反之不合法

这样我们就在 $O(\log n)$ 求出一个点是否在凸包内了

先补一个 $Graham$ 模板题的代码：

#include <bits/stdc++.h>
using namespace std;
namespace CZW
{
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	using lb=long double;
	constexpr lb eps=1e-9;
	struct V{
		lb x,y;
		V (lb _x=0,lb _y=0) : x(_x),y(_y) {}
	};
	V operator-(const V& a,const V& b){
		return {a.x-b.x,a.y-b.y};
	}
	lb cross(const V& a,const V& b){
		return a.x*b.y-a.y*b.x;
	}
	int sgn(const lb& x){
		if (x>eps) return 1;
		if (x< -eps)return -1;
		else return 0;
	}
	lb dot(const V& a,const V& b){
		return a.x*b.x+a.y*b.y;
	}
	void Main()
	{
		int n; cin>>n;
		vec<V> a(n+1,0);
		for (int i=1;i<=n;++i) cin>>a[i].x>>a[i].y;
		int base=1;
		for (int i=2;i<=n;++i){
			if (sgn(a[i].y-a[base].y)<0||(sgn(a[i].y-a[base].y)==0&&sgn(a[i].x-a[base].x)<0)){
				base=i;
			}
		}
		swap(a[1],a[base]);
		V o=a[1];
		sort(a.begin()+2,a.end(),[&](const V& a1,const V& a2)->bool{
			lb d=cross(a1-o,a2-o);
			return sgn(d)!=0?sgn(d)>0:dot(a1-o,a1-o)<dot(a2-o,a2-o);
		});
		vec<V> stk((n<<1)+1,0);
		int top=0;
		stk[++top]=a[1],stk[++top]=a[2];
		for (int i=3;i<=n;++i){
			while(top>=2&&sgn(cross(stk[top]-stk[top-1],a[i]-stk[top-1]))<=0) --top;
			stk[++top]=a[i];
		}
		stk[top+1]=a[1];
		lb ans=0;
		for (int i=1;i<=top;++i) {
			V u=stk[i+1]-stk[i];
			ans+=sqrtl(dot(u,u));
		}
		cout<<fixed<<setprecision(2)<<ans;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

Polygons CodeForces - 166B

进阶问题的板子，如果一个多边形在凸包内，则这个多边形每个点一定在凸包内。观察数据范围，显然 $O(nm)$ 是无法接受的，所以用进阶问题思路即可做到 $O(m \log n)$ 。

实现时注意是顺时针读入，把每个问题想清楚

#include<bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
    using ll = long long;
    using ull = unsigned long long;
    using i128 = __int128;
    struct V {
        ll x, y;
        V (ll _x = 0, ll _y = 0) : x(_x), y(_y) {   }
    };
    V operator -(const V& a, const V& b) {
        return {a.x - b.x, a.y - b.y};
    }
    ll cross(const V& a, const V& b) {
        return a.x * b.y - a.y * b.x;
    }
    void Main() {
        int n;
        cin >> n;
        vec<V> a(n + 1);
        for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y;
        V o = a[1];
        int m;
        cin >> m;
        auto chk = [&](const V & s)->bool {
            V u = s - o;
            if (cross(a[2] - o, u) >= 0) return false;
            if (cross(o - a[n], u) >= 0) return false;
            int l = 2, r = n;
            while(l < r - 1) {
                int mid = (l + r) >> 1;
                ll x = cross(a[mid] - o, u);
                if (x < 0) l = mid;
                else r = mid;
            }
//            cout<<l<<' '<<r<<endl;
            return cross(a[r] - a[l], s - a[l]) < 0;
        };
        bool f = true;
        for (int i = 1; i <= m; ++i) {
            V s;
            cin >> s.x >> s.y;
            if (!chk(s)) {
                f = false;
            }
        }
        cout << (f ? "YES" : "NO") << endl;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Test = 1;
//  cin>>Test;
    while(Test--) CZW::Main();
    return 0;
}

The Supersonic Rocket CodeForces - 1017E

再考虑一个凸包结合 $KMP$ 问题：

题目概述：给定两串点先求凸包，再判断两个凸包是否同构。

求凸包很简单，上面讲过了。那怎么判同构呢？（想了很久......

回归最初，考虑一个多边形的特征：边，角。那我们判断两个是否同构，就相当于判多边形的特征是否相同。

我们用一个结构体存对于一个点 $i$ ，到下个点 $i+1$ 的长度平方，关联两边的叉乘和点乘（反应这个角的 $sin$ 和 $cos$ ）

这样我们把二维凸包压成一个一维序列，接下来怎么做？

考虑到两个序列开始位置不同，相当于判断两个序列循环位移是否相同？这个就非常板子了，复制两份跑 $KMP$ 即可。

这样我们又做完了一个紫题！

#include <bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
	using ll = long long;
	using ull = unsigned long long;
	using i128 = __int128;
	void init() {
//		freopen("1.in","r",stdin);
//		freopen("my.out","w",stdout);
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout.tie(nullptr);
	}
	struct V {
		ll x, y;
		V (ll _x = 0, ll _y = 0) : x(_x), y(_y) { }
	};
	struct Node {
		ll len, v1, v2;
		Node (ll l = 0, ll _v1 = 0, ll _v2 = 0) : len(l), v1(_v1), v2(_v2) { }
		bool operator ==(const Node& other) {
			return len == other.len && v1 == other.v1 && v2 == other.v2;
		}
	};
	V operator -(const V& a, const V& b) {
		return {a.x - b.x, a.y - b.y};
	}
	ll cross(const V& a, const V& b) {
		return a.x * b.y - a.y * b.x;
	}
	ll dot(const V& a, const V& b) {
		return a.x * b.x + a.y * b.y;
	}
	int sgn(const ll& x) {
		if (x < 0) return -1;
		else if (x > 0) return 1;
		else return 0;
	}
	pair<vec<V>, int> get(vec<V>& a, int n) {
		int base = 1;
		for (int i = 2; i <= n; ++i) {
			if (a[i].y < a[base].y || (a[i].y == a[base].y && a[i].x < a[base].x)) {
				base = i;
			}
		}
//		cout<<"base:"<<base<<endl;
		swap(a[1], a[base]);
		V o = a[1];
		sort(a.begin() + 2, a.end(), [&](const V & xx, const V & yy)->bool{
			ll d = cross(xx - o, yy - o);
			return sgn(d) ? sgn(d) > 0 : dot(xx - o, xx - o) < dot(yy - o, yy - o);
		});
		vec<V> stk((n << 1) +2);
		int top = 0;
		stk[++top] = a[1], stk[++top] = a[2];
		for (int i = 3; i <= n; ++i) {
			while (top >= 2 && cross(stk[top] - stk[top - 1], a[i] - stk[top - 1]) <= 0) --top;
			stk[++top] = a[i];
		}
		stk[top + 1] = a[1], stk[0] = a[n];
		return {stk, top};
	}
	void Main() {
		int n, m;
		cin >> n >> m;
		vec<V> a1(n + 1), a2(m + 1);
		for (int i = 1; i <= n; ++i) cin >> a1[i].x >> a1[i].y;
		for (int i = 1; i <= m; ++i) cin >> a2[i].x >> a2[i].y;
		auto [ans1, cnt1] = get(a1, n);
		auto [ans2, cnt2] = get(a2, m);
//		cout<<endl;
//		for (auto [x,y]:ans1) cout<<x<<' '<<y<<endl;
//		cout<<endl;
//		for (auto [x,y]:ans2) cout<<x<<' '<<y<<endl;
		vec<Node> t1((n << 1) +2), t2(n + 1);
		for (int i = 1; i <= cnt1; ++i) {
			V u1 = ans1[i + 1] - ans1[i], u2 = ans1[i] - ans1[i - 1];
			t1[i] = {dot(u1, u1), cross(u2, u1), dot(u2, u1)};
		}
		for (int i = 1; i <= cnt2; ++i) {
			V v1 = ans2[i + 1] - ans2[i], v2 = ans2[i] - ans2[i - 1];
			t2[i] = {dot(v1, v1), cross(v2, v1), dot(v2, v1)};
		}
		for (int i = 1; i < cnt1; ++i) {
			t1[i + cnt1] = t1[i];
		}
		auto kmp = [&]() {
			if (cnt2 == 0) return true;
			vec<int> nxt(cnt2 + 1, 0);
			for (int i = 2, j = 0; i <= cnt2; ++i) {
				while (j && !(t2[i] == t2[j + 1])) j = nxt[j];
				if (t2[i] == t2[j + 1]) ++j;
				nxt[i] = j;
			}
			for (int i = 1, j = 0; i <= (cnt1 << 1) -1; ++i) {
				while (j && !(t1[i] == t2[j + 1])) j = nxt[j];
				if (t1[i] == t2[j + 1]) ++j;
				if (j == cnt2) return true;
			}
			return false;
		};
		cout << (kmp() ? "YES" : "NO");
	}
}
int main() {
	CZW::init();
	int Test = 1;
//	cin >> Test;
	while (Test--)
		CZW::Main();
	return 0;
}

鬼知道我调了多久，没招了。。~~@cjdst怎么WA了~~

当然还有旋转卡壳，开个坑，学会了再补。。。

有帮助，赞一个

去预览

0/2000

全部评论 14

cjdst
置顶
妈妈

2026-07-27 来自广东
2
- cjdst
  回复
  cjdst
  @Eucatastrophe‌ @Xylophone @🥥 @prediction 支持一下
  
  2026-07-27 来自广东
  1
- 🥥
  回复
  cjdst
  orz
  
  2026-07-27 来自上海
  0
- Asdfre
  回复
  cjdst
  吓哭了
  
  2026-07-27 来自广东
  0
Lin.Zikang
$\text{\Huge\color{orange}\fbox{大佬！}}$

2026-07-28 来自浙江
1
MYJ888
高级不火？

2026-07-28 来自浙江
1
- Asdfre
  回复
  MYJ888
  您比我强
  
  2026-07-28 来自广东
  1
- MYJ888
  回复
  Asdfre
  我去，我看都看不懂
  
  2026-07-29 来自浙江
  1
- MYJ888
  回复
  Asdfre
  虽然说课已经听到2叉树了，但水平连深搜都不会
  
  2026-07-29 来自浙江
  1
Eucatastrophe‌
你 GO 大蛇越来越多了

2026-07-27 来自浙江
1
- Asdfre
  回复
  Eucatastrophe‌
  %%%\bx
  
  2026-07-27 来自广东
  0
oh my god
老一辈坚持手搓

2026-07-28 来自浙江
0
清莲於泥(施嘉馨)
太有实力了！

2026-07-28 来自浙江
0
wcqk
严肃关注

2026-07-28 来自湖北
0
古希腊掌管AC和WA的神
orz

2026-07-28 来自上海
0
༺ཌༀཉི༒:lil:༒༃ༀད

2026-07-27 来自广东
0
🥥
%%%计算几何大神

2026-07-27 来自上海
0
- Asdfre
  回复
  🥥
  您比我强
  
  2026-07-27 来自广东
  0
- 🥥
  回复
  Asdfre
  您比我强
  
  2026-07-27 来自上海
  0
- 🥥
  回复
  Asdfre
  我弱弱，您强强
  
  2026-07-28 来自上海
  0
prediction
严肃预习

2026-07-27 来自浙江
0
- Asdfre
  回复
  prediction
  您比我强
  
  2026-07-27 来自广东
  0
- prediction
  回复
  Asdfre
  别P了大佬，您洛谷名是啥？
  
  2026-07-27 来自浙江
  0
- Asdfre
  回复
  prediction
  www
  
  2026-07-28 来自广东
  0
prediction
tql

2026-07-27 来自浙江
0
Eucatastrophe‌
CZW

2026-07-27 来自浙江
0
- 🥥
  回复
  Eucatastrophe‌
  陈臻武（无端联想）
  
  2026-07-28 来自上海
  0
- Asdfre
  回复
  🥥
  吓哭了
  
  2026-07-29 来自广东
  0
Asdfre
d

2026-07-27 来自广东
0