洛谷 – P8000 – [WFOI – 01] 循环节
|
题解
|
268

1451 字
|
37 分钟

题意

题面地址

给定点集 $a$，已知 $a$ 是由任意三点不共线，任选四点均非梯形或平行四边形的点集 $b$ 延向量 $\vec x$ 连续移 $z$ 次得到的。每次移动后，原来的点集仍存在。

求 $(b,\vec x,z)$，用坐标形式表示 $\vec x$.

若有多解，求出 $z$ 最大的；若还有多解，输出任意一组即可。

保证无论 $b$ 延 $\vec x$ 移多少次，都不会有重点。

$1\leq n\leq 10^5$，点的坐标范围 $\in(-10^9, 10^9)$，均为整数，保证有解。

写在前面

代码中使用了向量类，可参考题解最后一部分的代码。

为方便取模等操作，代码中下标均从 $0$ 开始记录。

求 $b$

假设我们已经求出了 $\vec x$ 和 $z$，现在想求出原点集 $b$。

可以发现，点 $p\in b \Leftrightarrow p-\vec x\notin a$，因为如果一个点是经过平移操作后才得到的，$p-\vec x$ 一定存在于点集 $a$ 中。

坐标范围较大，需要用到 std::map 并重载运算符。

注意特殊处理 $z=0$ 的情况。

vector<int> b;
void calc_b() { //利用 map 求 b 集合
	map<Point, bool> mp;
	if(z == 0) x.x = inf, x.y = inf;
	for(int i = 0; i < n; i++) mp[p[i]] = 1;
	for(int i = 0; i < n; i++) {
		if(mp[p_in[i] - x] == 0) {
			b.push_back(i);
		}
	}
}

求 $\vec x$ 和 $z$

求 $\vec x$ 和 $z$ 的过程较为复杂。

一种暴力的方法是，$\mathcal{O}(n^2)$ 枚举所有点对 $(u,v)$，检验 $\vec x=$ 是否合法。

注意到，由于点都是平移出来的，所以 $\vec x$ 会被枚举到很多遍，但我们只需要一遍。

可以先随便举例观察一些性质。

P8000-1

旋转卡壳

如上图，$\vec x=(2, 1)$，$b=\{A,B,C,D\}$，$a=\{A,A^{\prime},A^{\prime\prime},B,B^{\prime},B^{\prime\prime},C,C^{\prime},C^{\prime\prime},D,D^{\prime},D^{\prime\prime}\}$.

可以发现，$\vec x$ 一定会出现在凸包的边界上。并且，存在凸包上的一条边，完整地包含：某个起点以及由其平移 $z$ 次得到的所有点。

又注意到题目限制：没有任意四个起点构成梯形或平行四边形。

所以先求凸包，然后在凸包上跑一遍旋转卡壳。若当前的两条平行线经过 $\geq 4$ 个点，则这些点一定不都是起点。我们取出平行线通过的点，利用其求出 $\vec x$ 和 $z$，方法见下一部分。

形式化地，假设凸包上的点按逆时针顺序编号，当前枚举到的线段是 $(i,i+1)$，通过旋转卡壳，我们找到最大的范围 $[j,k]$，其满足：编号在 $[j,k]$ 区间内的点共线，它们所在的直线与线段 $(i,i+1)$ 平行。若 $k-j>0$，则我们利用 $[j,k]$ 这些点求出 $\vec x$ 和 $z$.

处理直线上的问题

进一步把问题抽象，我们得到有 $n$ 个共线的点 $p_0,p_1,\cdots,p_{n-1}$，要利用它们求出 $\vec x$ 和 $z$.

分类讨论，共三种情况，分别 $\rm{check}$ 一下就行了。

情况一

P8000-2

只包含一个起点，$\vec x$ 为 $p_0$ 和 $p_1$ 之间的向量。

因为凸包编号有序，所以起点为 $p_0$，$x=(p_{1x}-p_{0x}, p_{1y}-p_{0y})$，$z=n-1$.

curx = p[1] - p[0], ok = 1;
for(int t = 1; t < n; t++) {
    if(p[t] != p[0] + t * curx) {
        ok = 0, tmp = t;
        break;
    }
}
if(ok) {
    if(n - 1 > z) z = n - 1, x = curx;
    return;
}

情况二

P8000-3

$\vec x$ 依旧为 $p_0$ 和 $p_1$ 之间的向量

包含两个起点，且两个起点延伸出来的线段，互相不交叉。

在情况一中，我们用 $\rm{tmp}$ 存储了第一个不满足情况一的点的编号。

由此，所以起点为 $p_0$ 和 $p_{\operatorname{tmp}}$，$x=(p_{1x}-p_{0x}, p_{1y}-p_{0y})$，在 $\rm{check}$ 的同时计算 $z$ 就可以了。

curx = p[1] - p[0];
ok = 1, cnt1 = 0, cnt2 = 0;
for(int t = 1; t < n; t++) if(t != tmp) {
    if(p[t] == p[0] + (cnt1 + 1) * curx) cnt1++;
    else if(p[t] == p[tmp] + (cnt2 + 1) * curx) cnt2++;
    else { ok = 0; break; }
}
if(ok) {
    z = cnt1, x = curx;
    return;
}

情况三

P8000-4

$\vec x$ 为 $p_0$ 和 $p_2$ 之间的向量，思考一下可知，这并不会被包含到情况二中。

起点为 $p_0$ 和 $p_1$，$\vec x=(p_{2x}-p_{0x}, p_{2y}-p_{0y})$.

$\rm{check}$ 方法类似，注意要保证 $n>2$.

curx = p[2] - p[0];
ok = 1, cnt1 = 0, cnt2 = 0;
for(int t = 2; t < n; t++) {
    if(p[t] == p[0] + (cnt1 + 1) * curx) cnt1++;
    else if(p[t] == p[1] + (cnt2 + 1) * curx) cnt2++;
    else { ok = 0; break; }
}
if(ok) {
    z = cnt1, x = curx;
    return;
}

代码实现

需特殊处理所有点共线的情况。在我的 这份AC代码 中，分开处理了所有点共线的部分，可以参考。

下面的实现将特殊情况在旋转卡壳中一并处理，详见代码注释。

由于旋转卡壳的循环性，下面的实现中有大量取模运算，并不利于阅读。分类讨论中的代码风格更适合阅读。

int n, z; Point x;
Point p_in[MAXN], p[MAXN], ch[MAXN];
void calc_x_and_z() { //求 x和 z
	bool collinear = true; //collinear = true <-> 所有点都共线
	for(int i = 1; i < n; i++) {
		if((p[i - 1] - p[0]) * (p[i] - p[0]) != 0) {
			collinear = false;
		}
	}
	int siz, j, k; //siz凸包大小, j/k用于旋转卡壳
	int ok, tmp, cnt1, cnt2; //flag, 第一个不满足条件的点, 两个起点时用到的指针
	Point curx;
	if(collinear) { //所有点共线，特殊处理，认为所有点都在凸包里
		siz = n;
		memcpy(ch, p, sizeof(p)); sort(ch, ch + n);
	} else { //不都共线，求凸包
		siz = Convex_hull(n, p, ch), j = 1, k = 1;
		ch[siz] = ch[0]; ch[siz + 1] = ch[1];
	}
	for(int i = 0; i < siz; i++) { //旋转卡壳，(i, i+1)
		if(collinear) { //所有点共线时，只需要算一遍
			if(i > 0) break;
			j = 0, k = n - 1;
		} else { //否则正常旋转卡壳
			j = k;
			while((ch[i] - ch[j+1]) * (ch[i+1] - ch[j+1]) >
				(ch[i] - ch[j  ]) * (ch[i+1] - ch[j  ]))
				j = (j + 1) % siz;
			k = j;
			while((ch[i] - ch[k+1]) * (ch[i+1] - ch[k+1]) ==
				(ch[i] - ch[k  ]) * (ch[i+1] - ch[k  ]))
				k = (k + 1) % siz;
		}
		//[j, k]内的点均共线，所在直线与(i, i+1)平行
		if(k == j) continue;
		if(k == (j + 1) % siz) {
			if(1 > z) z = 1, x = ch[j+1] - ch[j];
			continue;
		}
		//1. 只有一个起点，curx = ch[j+1] - ch[j]
		curx = ch[j + 1] - ch[j];
		ok = 1, cnt1 = 0;
		for(int t = (j + 1) % siz; t != (k + 1) % siz; t = (t + 1) % siz) {
			if(ch[t] != ch[j] + (cnt1 + 1) * curx) {
				ok = 0, tmp = t;
				break;
			} cnt1++;
		}
		if(ok) {
			if(cnt1 > z) z = cnt1, x = curx;
			continue;
		}
		//2. 有两个起点 & curx = ch[j+1] - ch[j]，起点为 ch[j] 和 ch[tmp]
		curx = ch[j + 1] - ch[j];
		ok = 1, cnt1 = 0, cnt2 = 0;
		for(int t = (j + 1) % siz; t != (k + 1) % siz; t = (t + 1) % siz) if(t != tmp) {
			if(ch[t] == ch[j] + (cnt1 + 1) * curx) cnt1++;
			else if(ch[t] == ch[tmp] + (cnt2 + 1) * curx) cnt2++;
			else { ok = 0; break; }
		}
		if(ok && cnt1 == cnt2) {
			if(cnt1 > z) z = cnt1, x = curx;
			continue;
		}
		//3. 两个起点 & curx = ch[j+2] - ch[j]，起点为 ch[j] 和 ch[j+1]
		curx = ch[j + 2] - ch[j];
		ok = 1, cnt1 = 0, cnt2 = 0;
		for(int t = (j + 2) % siz; t != (k + 1) % siz; t = (t + 1) % siz) {
			if(ch[t] == ch[j] + (cnt1 + 1) * curx) cnt1++;
			else if(ch[t] == ch[j + 1] + (cnt2 + 1) * curx) cnt2++;
			else { ok = 0; break; }
		}
		if(ok && cnt1 == cnt2) {
			if(cnt1 > z) z = cnt1, x = curx;
			continue;
		}
	}
}

其他部分的代码实现

两个主要函数的代码，在上文已经给出。

这里仅包含：向量类的定义、凸包的求法、主函数。

const int MAXN = 1e5 + 10, inf = 0x3f3f3f3f;
struct Point{ //向量类
	int x, y;
	Point(){};
	Point(int a, int b): x(a), y(b) {}
	Point(Point a, Point b): x(b.x - a.x), y(b.y - a.y) {}
	friend Point operator + (const Point &a, const Point &b) {
		return Point(a.x + b.x, a.y + b.y);
	}
	friend Point operator - (const Point &a, const Point &b) {
		return Point(a.x - b.x, a.y - b.y);
	}
	friend bool operator == (const Point &a, const Point &b) {
		return a.x == b.x && a.y == b.y;
	}
	friend bool operator != (const Point &a, const Point &b) {
		return a.x != b.x || a.y != b.y;
	}
	friend Point operator * (const int &a, const Point &b) {
		return Point(a * b.x, a * b.y);
	}
	friend Point operator * (const Point &a, const int &b) {
		return Point(a.x * b, a.y * b);
	}
	friend int operator * (const Point &a, const Point &b) {
		return a.x * b.y - a.y * b.x;
	}
	friend int operator & (const Point &a, const Point &b) {
		return a.x * b.x + a.y * b.y;
	}
	friend bool operator < (const Point &a, const Point &b) {
		return (a.x < b.x) || (a.x == b.x && a.y < b.y);
	}
};

inline bool check(Point s1, Point s2, Point p) {
	return Point(s2, s1) * Point(s1, p) >= 0; //凸包保留共线的点
}
int Convex_hull(int n, Point *p, Point *ret) { //求二维凸包，返回值为凸包大小
	sort(p, p + n);
	int top = -1;
	for (int i = 0; i < n; i++) {
		while (top > 0 && !check(ret[top], ret[top - 1], p[i]))
			top--;
		ret[++top] = p[i];
	}
	int k = top;
	for (int i = n - 2; i >= 0; i--) {
		while (top > k && !check(ret[top], ret[top - 1], p[i]))
			top--;
		ret[++top] = p[i];
	}
	return top;
}

signed main() {
	n = read();
	for(int i = 0; i < n; i++) p_in[i].x = read(), p_in[i].y = read();
	for(int i = 0; i < n; i++) p[i] = p_in[i];

	calc_x_and_z();
	calc_b();

	printf("%lld\n", (long long)b.size());
	for(int i = 0; i < b.size(); i++) printf("%lld ", b[i] + 1); putchar('\n');
	printf("%lld %lld\n%lld\n", x.x, x.y, z);
	return 0;
}

 

旋转卡壳计算几何
暂无评论

发送评论 编辑评论

 
 
 
 
 
 
 
  
  
  
   
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
  
上一篇
下一篇 
  推荐文章
置顶 – 计算几何
 
洛谷 – P7529 – 动态凸包与CDQ分治