牛客 NC15086 - 向左走

题目大意

牛客 NC15086「向左走」。多组数据（不超过 10 组）。每组给 $n$ 根杆子（ $1\le n\le 1000$ ），坐标范围 $[1,1000]$ 且互不重合。

你拿着绳子从某根杆子出发，规则有四条：只能向左转或直行（绝不右拐）、只能走直线、走过的路不能与自己相交、每根杆子最多经过一次。起点固定为 $y$ 最小、 $y$ 相同取 $x$ 最小 的那根杆子。

目标：经过尽量多的杆子（其实可以全部经过），输出经过杆子的编号顺序。

样例

4 根杆子 $1(3,1)\,2(7,1)\,3(5,3)\,4(5,5)$ ，输出 1 2 4 3 。从最低点 $1$ 出发，外圈是三角形 $\{1,2,4\}$ 逆时针描一遍，剩下的 $3$ 在最里面，最后串上。

思路讲解

一句话

洋葱剥皮（onion peeling）螺旋：从最低点出发，沿点集的凸包逆时针描一圈；描完把这一圈的点剥掉，剩下的点又是一个点集，对它再描一圈，像蚊香一样越绕越往里。难点全在两层之间怎么衔接——内层的入口不能随便选，否则会右转或自交。

「只能向左转」= 朝向角单调逆时针旋转

你每到一根杆子要么直行要么左拐、永远不右拐，等价于说：你的前进方向（朝向角）只会朝一个方向累积旋转，绝不回头。这是个很强的约束——它把"路径"逼成一条逆时针卷进去的螺旋。

沿最外圈 = 逆时针描凸包

站在最低点、朝向只能左转，那么"贴着最外圈走出来的轨迹"恰好就是把点集的凸包按逆时针描一遍：第一步沿凸包下边迈出去（朝最贴右的方向，使其余所有点都在你左手边），之后每到一个顶点左拐，逆时针绕完外圈。所以第一步方向就被钉死了。

关键不变量：起点是全局最低点，外层凸包按逆时针（CCW）输出，第一条边朝向使所有点在左手侧。

钻进内层 = 递归同类子问题

外圈只串起了边界上的杆子，里面还有没碰到的。绕完一圈快回到起点时往里钻一层——而内部剩下的杆子本身又是一个点集，面对的规则一模一样（从它的最外层开始、只能左转、不自交）。所以整个算法就是反复做同一个动作：

1. 对当前剩余点求凸包（CCW），输出这一层；

2. 把这层的点删掉，对剩点重复。

关键①：内层入口怎么选（续接式入口，不是重置最低点）

这是本题最容易写错、也是我这次真栽进去的地方。一个自然但错误的写法是：对每一层都调用"找该层字典序最小点、旋转到开头"（即 reorder_polygon）。第一层这么做对（全局最低点就是螺旋起点），但内层这么做就错了——内层会从它自己的最低点起头，而那个点未必接得上上一层的螺旋，会在层边界右转或让连接边穿过内层造成自交。

正确做法是续接式入口：设上一层走完停在末顶点 $e$ ，进入 $e$ 时的前进方向是 $\overrightarrow{d}$ 。对内层这个 CCW 多边形，入口顶点 $w$ 取使 $\overrightarrow{d}$ 逆时针转到 $\overrightarrow{w-e}$ 的转角最小的那一个，再从 $w$ 起按 CCW 走完内层。直觉就是：朝向只能继续逆时针转，那就贴着当前方向最小幅度地左转钻进去，绳子贴着自己往里收，绝不会右拐、也不会去穿别的边。

$$w = \arg\min_{v \in L}\ \mathrm{ccwAngle}(\overrightarrow{d},\ \overrightarrow{v - e})$$

红色结论：内层入口必须续接上一层的前进方向（极角基准 = 上一层末顶点 $e$ ），绝不能重置成内层自己的最低点。后者就是 WA 的来源。

这条规则在 5000 组随机点集上 100% 产出"全程左转 + 无自交"的合法路径，样例也吻合。

关键②：共线层的退化处理

剥到某一层时，如果剩下的点恰好全共线，凸包退化成一条线段。此时弱凸包（保留共线点）的 Andrew 扫描会折返：上行扫一遍再下行扫回来，输出形如 A B C B 的重复序列——同一个点被走两遍，输出就不是全排列，直接 WA。

处理：对一层的凸包用有向面积判退化（面积为 0 即全共线），退化时这层的点已经按排序顺序排好且互不重复，直接当一条线"单程"返回即可，不折返。这一步是 $O(n)$ 的，不要写成两两比对的 $O(n^2)$ 去重。

复杂度

每层一次凸包 $O(n\log n)$ ，最多 $O(n)$ 层，整体 $O(n^2\log n)$ 。 $n\le 1000$ 、不超过 10 组，稳过。

📎 动画与源码

我做了一个交互式 HTML 演示，可以一步步点 Step 看每个拐点的转向叉积，对比"修正前 vs 修正后"内层入口的差别（右转/自交怎么发生、续接式入口怎么修好）。本体和关键帧截图见附件节。

AC 代码

AC 提交（vjudge）

完整源码较长（含整套几何模板），折叠如下：

展开完整源码

// teamname: Gospel_rock
/**
 * Problem: 向左走
 * Contest: 
 * Judge: NowCoder
 * URL: https://ac.nowcoder.com/acm/problem/15086
 * Created: 2026-05-22 11:04:13
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define fsp(x) fixed<<setprecision(x)

using namespace std;

#if 1 && defined(LOCAL)
// @formatter:off
namespace DBG {
	template<typename T> void debug(T x);
	void debug(bool x);
	void debug(string x);
	template<typename T> void debug(vector<T> v);
	template<typename T, size_t N> void debug(array<T, N> v);
	template<typename T> void debug(set<T> s);
	template<typename T, typename U> void debug(pair<T, U> p);
	template<typename T, typename U> void debug(map<T, U> m);
	template<typename, typename = void> constexpr bool _has_iter_v = false;
	template<typename T> constexpr bool _has_iter_v<T, void_t<decltype(declval<T>().begin()), decltype(declval<T>().end())>> = true;
	template<typename T>
	void debug(T x) { cerr << x; } void debug(bool x) { cerr << (x ? "T" : "F"); } void debug(string x) { cerr << '"' << x << '"'; }
	template<typename T> void debug(vector<T> v) { constexpr bool nested = _has_iter_v<T>; int n = v.size(); cerr << "["; for (int i = 0; i < n; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n  "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (n) cerr << "\n"; } cerr << "]"; }
	template<typename T, size_t N> void debug(array<T, N> v) { constexpr bool nested = _has_iter_v<T>; cerr << "["; for (size_t i = 0; i < N; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n  "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (N) cerr << "\n"; } cerr << "]"; }
	template<typename T> void debug(set<T> s) { cerr << "{"; int f = 0; for (auto x: s) { if (f++) cerr << ", "; debug(x); } cerr << "}"; }
	template<typename T, typename U> void debug(pair<T, U> p) { cerr << "("; debug(p.first); cerr << ", "; debug(p.second); cerr << ")"; }
	template<typename T, typename U> void debug(map<T, U> m) { cerr << "{"; int f = 0; for (auto &[k, v]: m) { if (f++) cerr << ", "; debug(k); cerr << ": "; debug(v); } cerr << "}"; }
	void _dbg() { cerr << endl; }
	template<typename T, typename... A> void _dbg(T x, A... a) { debug(x); if (sizeof...(a)) cerr << ", "; _dbg(a...); }
}
// @formatter:on
#define dbg(x...) cerr << "[" << setw(7) << #x << "] = ", DBG::_dbg(x)
#define cend cerr<<"\n---------------------------------------------------\n"
#define cEnd cerr<<"\n***************************************************\n"
#define myAssert(...) assert((__VA_ARGS__))
#else
#define dbg(x...) 11
#define cend 45
#define cEnd 14
#define myAssert(x) 14
#endif

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);

ll lT, testcase;

/*
 *
 */


/*
 * 2026-2-3  增加编译器识别 Real 类型功能
 * 2026-3-19 增加了从斜率式和一般式构造 Line
 * 2026-5-4  几何模板大改（QOJ 784 沉淀）：新增 isqrt / sqrtL、cross 三参数重载、polygonSignedArea，reorder_polygon 整体判向，isConvex 加 strict 参数，新增凸多边形直径旋转卡壳
 * 2026-5-5  Luogu P16223 沉淀：Point 加 id 字段，convex_diameter 加 n <= 2 退化特判，新增 furthest_pair_of_point
 * 2026-5-6  P3187 沉淀：getintersect 加浮点 assert + 显式 (DB) cross，make_convex_hull 加 strict 参数，新增 minimum_rectangle_cover
 * 2026-5-11 几何全面模板化：Point / Line 改 template<class T>，T 自动分流 ll / i128 / DB
 * 2026-5-12 加入了 Circle 类
 * 2026-5-13 加入了 half_plane_cut 和 unique_line_polar_angle_sort，加入了隐式转换和转换方向
 * 2026-5-15 加入了 HullMode
 */

// floor(sqrt(n)), n >= 0；二分 + 防溢出
i128 isqrt(i128 n) {
	if (n <= 0) return 0;
	i128 lo = 0, hi = (i128)2e18; // sqrt(4e36) <= 2e18
	while (lo < hi) {
		i128 mid = lo + (hi - lo + 1) / 2;
		if (mid <= n / mid) lo = mid; // 等价 mid*mid <= n，避免 i128 平方溢出
		else hi = mid - 1;
	}
	return lo;
}

// 统一 sqrt 入口：浮点直接 sqrtl；整数（含 i128）走 isqrt + fraction，避免 (long double) i128 在 n > 2^53 时丢整数精度。
template<typename T>
long double sqrtL(T n) {
	if constexpr (is_floating_point_v<T>) {
		return sqrtl((long double)n);
	} else {
		i128 ni = (i128)n;
		if (ni <= 0) return 0;
		i128 i = isqrt(ni);
		long double id = (long double)i;
		long double rd = (long double)(ni - i * i);
		// sqrt(i^2 + r) = i * sqrt(1 + r/i^2)
		return id * sqrtl(1.0L + rd / (id * id));
	}
}

// x*x 安全平方: 整数升 i128 防溢出 (1000^2 不会溢, 但模板要扛 1e9 量级输入),
// 浮点原样 T*T 不动 (i128 没浮点意义).
template<class T>
auto squared(T x) {
	if constexpr (is_floating_point_v<T>) {
		return x * x;
	} else {
		return (i128)x * (i128)x;
	}
}

template<class T>
int sgn(T x) {
	if (-eps < x && x < eps) return 0;
	return x < 0 ? -1 : 1;
}

template<class T>
struct Point {
	T x, y;
	int id = -1; // 原始下标. -1 表示派生点 (+ - * 等算术结果) 或未赋值, id 无意义

	explicit Point(T x_ = 0, T y_ = 0) : x(x_), y(y_) {
	}

	// Point<U> -> Point<T> 隐式 (common_type 单调升档方向, U -> T 必须无损):
	// common_type_t<U, T> == T 才放行 (例 ll -> DB 通; DB -> ll 拦, 防 truncation)
	template<class U, class = enable_if_t<is_same_v<common_type_t<U, T>, T> > >
	Point(const Point<U> &o) : x((T)o.x), y((T)o.y), id(o.id) {
	}

	// 只对左值生效的复合运算符
	Point &operator+=(Point p) & {
		x += p.x, y += p.y;
		return *this;
	}

	Point &operator-=(Point p) & {
		x -= p.x, y -= p.y;
		return *this;
	}

	Point &operator*=(T t) & {
		x *= t, y *= t;
		return *this;
	}

	Point &operator/=(T t) & {
		x /= t, y /= t;
		return *this;
	}

	Point operator-() const { return Point(-x, -y); }

	friend Point operator+(Point a, Point b) { return a += b; }
	friend Point operator-(Point a, Point b) { return a -= b; }

	// 标量乘除: 返回 Point<common_type_t<T, U>> (C++14), 自动算公共类型
	// <ll,ll>=ll / <ll,DB>=DB / <DB,ll>=DB; R==T 走 copy ctor, R!=T 走 converting ctor
	template<class U>
	friend auto operator*(Point a, U b) {
		Point<common_type_t<T, U> > r = a;
		r *= b;
		return r;
	}

	template<class U>
	friend auto operator*(U a, Point b) {
		Point<common_type_t<T, U> > r = b;
		r *= a;
		return r;
	}

	template<class U>
	friend auto operator/(Point a, U b) {
		Point<common_type_t<T, U> > r = a;
		r /= b;
		return r;
	}

	friend bool operator<(Point a, Point b) {
		int sx = sgn(a.x - b.x);
		if (sx != 0) return a.x < b.x;
		return a.y < b.y;
	}

	friend bool operator>(Point a, Point b) { return b < a; }

	friend bool operator==(Point a, Point b) {
		return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
	}

	friend bool operator!=(Point a, Point b) { return !(a == b); }

	friend istream &operator>>(istream &is, Point &p) { return is >> p.x >> p.y; }
	friend ostream &operator<<(ostream &os, Point p) { return os << "(" << p.x << ", " << p.y << ")"; }

	auto norm() const {
		if constexpr (!is_floating_point_v<T>) {
			return (__int128_t)x * x + (__int128_t)y * y;
		} else {
			return x * x + y * y;
		}
	}

	DB abs() const { return sqrtL(norm()); }

	Point rot90() const {
		return Point(-y, x);
	}

	Point<DB> rot(DB ang) const {
		return Point<DB>(cosl(ang) * x - sinl(ang) * y, sinl(ang) * x + cosl(ang) * y);
	}

	// L1 范数 (曼哈顿) = |x| + |y|. 整型分支走 __int128_t 防溢出.
	auto normL1() const {
		auto ax = (x < 0 ? -x : x), ay = (y < 0 ? -y : y);
		if constexpr (!is_floating_point_v<T>) {
			return (__int128_t)ax + (__int128_t)ay;
		} else {
			return ax + ay;
		}
	}

	// Linf 范数 (切比雪夫) = max(|x|, |y|). 返回类型与 T 同.
	T normLinf() const {
		auto ax = (x < 0 ? -x : x), ay = (y < 0 ? -y : y);
		return ax > ay ? ax : ay;
	}
};

template<class T, class U>
auto cross(Point<T> a, Point<U> b) {
	// 在 T 为整数的时候，使用 __int128_t 整型进行计算
	//（改为这个非float，那么在类型为I128时，仍然可以计算）
	if constexpr (!is_floating_point_v<T> && !is_floating_point_v<U>) {
		return (__int128_t)a.x * b.y - (__int128_t)a.y * b.x;
	} else {
		return a.x * b.y - a.y * b.x;
	}
}

// 三点重载: 以 o 为原点, 算 (a - o) × (b - o)
// 用途: 判 3 点 turn (>0 左转, <0 右转, =0 共线) / 2 倍三角形有向面积 / 凸包面积扫描
template<class T, class U, class V>
auto cross(Point<T> o, Point<U> a, Point<V> b) {
	return cross(a - o, b - o);
}

template<class T, class U>
auto dot(Point<T> a, Point<U> b) {
	// 在 T 为整数的时候，使用 __int128_t 整型进行计算
	if constexpr (!is_floating_point_v<T> && !is_floating_point_v<U>) {
		return (__int128_t)a.x * b.x + (__int128_t)a.y * b.y;
	} else {
		return a.x * b.x + a.y * b.y;
	}
}

// 三点重载: 以 o 为原点, 算 (a - o) · (b - o)
// 用途: 判夹角钝/直/锐 (>0 锐, =0 直, <0 钝) / 投影长度的有符号 2 倍 / 点在线段上的位置判定
template<class T, class U, class V>
auto dot(Point<T> o, Point<U> a, Point<V> b) {
	return dot(a - o, b - o);
}

// 采用两点式
template<class T>
struct Line {
	Point<T> p1, p2;

	Line() = default;

	Line(Point<T> a, Point<T> b) : p1(a), p2(b) {
	}

	// Line<U> -> Line<T> 隐式 (common_type 单调升档方向, 同 Point converting ctor)
	template<class U, class = enable_if_t<is_same_v<common_type_t<U, T>, T> > >
	Line(const Line<U> &o) : p1(o.p1), p2(o.p2) {
	}

	// AC https://qoj.ac/submission/2146870
	Line(T k, T c) : p1(Point<T>(0, c)), p2(Point<T>(1, k + c)) {
	}

	friend bool operator<(Line a, Line b) {
		if (a.p1 != b.p1) return a.p1 < b.p1;
		return a.p2 < b.p2;
	}

	friend bool operator==(Line a, Line b) {
		if (a.p1 != b.p1) return false;
		if (a.p2 != b.p2) return false;
		return true;
	}

	friend istream &operator>>(istream &is, Line &e) {
		T a, b, c, d;
		is >> a >> b >> c >> d;
		e = Line(Point<T>(a, b), Point<T>(c, d));
		return is;
	}

	friend ostream &operator<<(ostream &os, Line l) {
		return os << "<" << l.p1 << ", " << l.p2 << ">";
	}
};

Line<DB> gen_line_from_general(DB a, DB b, DB c) {
	// 方向向量 (b, -a)
	Point<DB> p1, p2;
	if (b != 0) {
		p1 = Point<DB>(0, -c / b);
	} else {
		p1 = Point<DB>(-c / a, 0);
	}
	p2 = Point<DB>(p1.x + b, p1.y - a);
	return Line<DB>(p1, p2);
}

// 使用这个东西，Point 必须是 double 等浮点类型
template<class T, class U>
Point<DB> project(Point<T> p, Line<U> l) {
	Point<DB> vec = l.p2 - l.p1;
	//                        这个距离反正早除晚除都要除掉
	DB r = dot(vec, p - l.p1) / ((DB)vec.x * vec.x + vec.y * vec.y);
	return l.p1 + vec * r;
}

template<class T, class U>
Point<T> reflect(Point<T> p, Line<U> l) {
	Point<T> proj = project(p, l);
	return proj + proj - p;
}

mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

constexpr int ON_SEGMENT = 0;
constexpr int COUNTER_CLOCKWISE = 1;
constexpr int CLOCKWISE = -1;
constexpr int ONLINE_BACK = 2;
constexpr int ONLINE_FRONT = -2;

template<class T, class U>
int CCW(Point<T> p, Line<U> l) {
	Point<DB> a = l.p2 - l.p1;
	Point<DB> b = p - l.p1;
	if (sgn(cross(a, b)) > 0) {
		return COUNTER_CLOCKWISE;
	}
	if (sgn(cross(a, b)) < 0) {
		return CLOCKWISE;
	}
	if (sgn(dot(a, b)) < 0) {
		return ONLINE_BACK;
	}
	if (a.norm() < b.norm()) return ONLINE_FRONT;
	return ON_SEGMENT;
}

template<class T, class U>
bool isOrthogonal(Line<T> a, Line<U> b) {
	auto c = a.p2 - a.p1, d = b.p2 - b.p1;
	return !sgn(dot(c, d));
}

template<class T, class U>
bool isParallel(Line<T> a, Line<U> b) {
	auto c = a.p2 - a.p1, d = b.p2 - b.p1;
	return !sgn(cross(c, d));
}

template<class T, class U>
bool isSegIntersect(Line<T> a, Line<U> b) {
	// 判断线段相交
	return CCW(b.p1, a) * CCW(b.p2, a) <= 0 && CCW(a.p1, b) * CCW(a.p2, b) <= 0;
}

// bool isIntersectStrict(Line a,Line b){    // 判断线段相交
//     return CCW(b.p1,a)*CCW(b.p2,a)<0 && CCW(a.p1,b)*CCW(a.p2,b)<0;
// }
// p+tv=q+sw
// (p-q) x w+tv x w = 0     (利用叉乘乘以自身为0，消掉sw)
// t=-(p-q)x w/(vxw)
// 传入的是方向式  拿到的是两直线交点
template<class T, class U>
Point<DB> getintersect(const Line<T> &a, const Line<U> &b) {
	Point<DB> p = a.p1, v = a.p2 - a.p1, q = b.p1, w = b.p2 - b.p1;
	Point<DB> u = p - q;
	DB t = (DB)cross(w, u) / cross(v, w);
	return p + v * t;
}

// 距离平方（不开方）：旋转卡壳里 ans 反复更新，留到最后一次 sqrt
template<class T, class U>
auto distancePPNorm(const Point<T> &a, const Point<U> &b) {
	return (a - b).norm();
}

// L2 欧几里得距离 (sqrt 版, 用 long double). 整型坐标走 isqrt + fraction 不丢精度.
template<class T, class U>
DB distancePP(const Point<T> &a, const Point<U> &b) {
	return (a - b).abs();
}

// L1 曼哈顿距离 = |dx| + |dy|. 返回类型继承 normL1 (整型 -> __int128_t, 浮点 -> T).
template<class T, class U>
auto distancePPL1(const Point<T> &a, const Point<U> &b) {
	return (a - b).normL1();
}

// Linf 切比雪夫距离 = max(|dx|, |dy|). 返回类型 T.
template<class T, class U>
T distancePPLinf(const Point<T> &a, const Point<U> &b) {
	return (a - b).normLinf();
}

// 也可以用 project 来算
template<class T, class U>
DB distancePL(Point<T> p, Line<U> l) {
	auto val = cross(l.p1, l.p2, p);
	return sgn(val) * val / (l.p2 - l.p1).abs();
}

// AC https://qoj.ac/submission/2001668
template<class T, class U>
DB distancePS(Point<T> p, Line<U> l) {
	// 避免 distanceSS 调用的时候发生这个退化（即线段退化为了点）
	if (l.p1 == l.p2) {
		return (p - l.p1).abs();
	}
	auto t = l.p2 - l.p1;
	if (sgn(dot(t, p - l.p1)) < 0) {
		return (p - l.p1).abs();
	}
	if (sgn(dot(t, p - l.p2)) > 0) {
		return (p - l.p2).abs();
	}
	return distancePL(p, l);
}

// AC https://qoj.ac/submission/2001588
template<class T, class U>
DB distanceSS(Line<T> a, Line<U> b) {
	if (isSegIntersect(a, b)) return 0;
	return min({distancePS(a.p1, b), distancePS(a.p2, b), distancePS(b.p1, a), distancePS(b.p2, a)});
}

// === polygonSignedArea + polygonArea (espanso :polygonArea, 拆自 :Point)
//     依赖: :Point 基础模板 (用到 cross)
// 多边形 2 倍有向面积 (不除 2 以保持整数精度).
// 返回类型 auto 自动跟 cross 走 (整数 Real → i128, 浮点 Real → Real).
// > 0: CCW; < 0: CW; == 0: 退化 (全共线 / 自交).
// 用途: polygonArea (取 abs / 2 得真面积) / reorder_polygon (取符号判方向).
template<class T>
auto polygonSignedArea(const vector<Point<T> > &poly) {
	auto res = cross(Point<T>(), Point<T>()); // 零值, 类型由 cross 继承
	size_t n = poly.size();
	for (size_t i = 0; i < n; ++i) {
		res += cross(poly[i], poly[(i + 1) % n]);
	}
	return res;
}

template<class T>
DB polygonArea(const vector<Point<T> > &poly) {
	auto s = polygonSignedArea(poly);
	if (s < 0) s = -s;
	return (DB)s / 2.0;
}

// === reorder_polygon (espanso :reorderPolygon, 拆自 :Point) ===
// 按照逆时针方向整齐排列，以 y 最小，然后 x 小的点开始
template<class T>
void reorder_polygon(vector<Point<T> > &poly) {
	ll n = poly.size();
	// 用 polygonSignedArea 判方向, 不依赖局部前三点 cross
	// (含共线点的 polygon 在前三点共线时, 局部判方向会误判为 CW)
	if (sgn(polygonSignedArea(poly)) < 0) {
		reverse(poly.begin(), poly.end());
	}
	// 找到 y 最小，然后 x 小的点
	ll pos_mn = 0;
	for (int i = 1; i < n; ++i) {
		if (poly[i].y < poly[pos_mn].y || (poly[i].y == poly[pos_mn].y && poly[i].x < poly[pos_mn].x)) {
			pos_mn = i;
		}
	}
	// Performs a left rotation on a range of elements
	// 向左循环移动，把 pos_mn 移动到第一个 [0]
	rotate(poly.begin(), poly.begin() + pos_mn, poly.end());
}


// === HullMode + make_convex_hull (espanso :makeConvexHull, 拆自 :Point)
//     依赖: :Point 基础模板
enum HullMode { HULL_FULL, HULL_LOWER, HULL_UPPER };

// strict = true:  严格凸包 (不保留三点共线的中间点)
// strict = false: 弱凸包    (保留三点共线的中间点), 题目要求"凸包上所有点"时用
template<class T>
vector<Point<T> > make_convex_hull(vector<Point<T> > A, bool strict, HullMode hull_mode) {
	size_t n = A.size();
	if (n <= 2) {
		// 特判
		return A;
	}
	vector<Point<T> > ans(n * 2);
	// Andrew 扫描: 排序键按 hull_mode 选.
	// HULL_LOWER / HULL_UPPER 是相对 X 扫描定义的, 按 X 排序 (X 相同按 Y), 与原行为字节级一致.
	// HULL_FULL 按 Y 排序 (Y 相同按 X): 整圈凸包天然从「Y 最小 (再 X 最小)」点起头且仍是 CCW,
	//   剥层螺旋第一层直接拿到「最低点起步」, 不必再 reorder_polygon 找最低点 -- 这就是本改动的意义.
	if (hull_mode == HULL_FULL) {
		sort(A.begin(), A.end(), [](const Point<T> &a, const Point<T> &b) {
			return a.y != b.y ? a.y < b.y : a.x < b.x;
		});
	} else {
		sort(A.begin(), A.end());
	}
	// strict 时 cross == 0 共线也弹; 弱凸只在 cross < 0 凹陷时弹
	auto fail = [&](ll s) { return strict ? s >= 0 : s > 0; };
	int now = -1;
	for (int i = 0; i < n; i++) {
		// 维护下凸包
		while (now > 0 && fail(sgn(cross(A[i], ans[now], ans[now - 1])))) {
			now--; // 弹出栈顶，因为它会导致凹陷 (strict 时还会弹掉共线)
		}
		ans[++now] = A[i];
	}
	if (hull_mode == HULL_LOWER) {
		ans.resize(now + 1);
		return ans;
	}
	int pre = now;
	// 从右向左扫描所有点（注意是从 n-2 开始，因为 n-1 已经在栈顶了）
	for (int i = n - 2; i >= 0; i--) {
		// 维护上凸包
		while (now > pre && fail(sgn(cross(A[i], ans[now], ans[now - 1])))) {
			now--;
		}
		ans[++now] = A[i];
	}
	if (hull_mode == HULL_UPPER) {
		return vector<Point<T> >(ans.begin() + pre, ans.begin() + now + 1);
	}
	ans.resize(now);
	// HULL_FULL: 因上面按 Y 排序, 这里已天然是「Y 最小点起头 + CCW」.
	// 退化处理: 输入点全共线时凸包退化成线段, 弱凸包会折返成重复序列 (如 A B C B);
	// 有向面积为 0 即退化, 此时 A 已按 Y 排好序且点互异, 就是沿线单程, 直接返回 (O(n), 不折返).
	if (sgn(polygonSignedArea(ans)) == 0 && !strict) {
		return A;
	}
	return ans;
}

// ===== 圆 (Circle) =====

// 圆弧 from -> to 的逆时针弧角差 [0, 2pi), 不是 abs(to - from)
static DB ccw_angle(DB theta_from, DB theta_to) {
	DB d = std::fmod(theta_to - theta_from, 2 * PI);
	if (d < 0) d += 2 * PI;
	return d;
}

// 向量版: 从方向向量 from 逆时针转到方向向量 to 的角 [0, 2pi).
// 用单次 atan2(cross, dot) (cross 当 sin 分量 / dot 当 cos 分量), 比两次 atan2 相减稳.
template<class T, class U>
static DB ccw_angle(Point<T> from, Point<U> to) {
	DB d = std::atan2((DB)cross(from, to), (DB)dot(from, to));
	if (d < 0) d += 2 * PI;
	return d;
}

ll N;

void Solve() {
	vector<Point<ll> > poly(N);
	for (auto &p: poly) {
		cin >> p.id;
		cin >> p;
	}
	vector<Point<ll> > backup;
	vector<char> vis(1000 + 2);
	vector<Point<ll> > ans;
	ans.reserve(N);
	// do {
	// 	auto convex_poly = make_convex_hull(poly, false, HULL_FULL);
	// 	for (const auto &p: convex_poly) {
	// 		vis[p.id] = 1;
	// 		ans.push_back(p);
	// 	}
	// 	backup.clear();
	// 	for (const auto &p: poly) {
	// 		if (!vis[p.id]) {
	// 			backup.push_back(p);
	// 		}
	// 	}
	// 	swap(backup, poly);
	// 	if (poly.empty()) {
	// 		break;
	// 	}
	// } while (false);
	while (true) {
		auto convex_poly = make_convex_hull(poly, false, HULL_FULL);
		DB mn_angle = INFINITY;
		ll mn_pos = 0;
		if (SZ(ans) >= 2) {
			for (int i = 0; i < SZ(convex_poly); ++i) {
				Point<ll> from = ans.rbegin()[0] - ans.rbegin()[1], to = convex_poly[i] - ans.rbegin()[0];
				DB angle = ccw_angle(from, to);
				if (angle < mn_angle) {
					mn_pos = i;
					mn_angle = angle;
				}
			}
		}
		rotate(convex_poly.begin(), convex_poly.begin() + mn_pos, convex_poly.end());
		for (const auto &p: convex_poly) {
			vis[p.id] = 1;
			ans.push_back(p);
		}
		backup.clear();
		for (const auto &p: poly) {
			if (!vis[p.id]) {
				backup.push_back(p);
			}
		}
		swap(backup, poly);
		if (poly.empty()) {
			break;
		}
	}
	for (auto &p: ans) {
		cout << p.id << " ";
	}
	cout << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif


	while (cin >> N)
		Solve();
	return 0;
}

/*
AC
https://vjudge.net/solution/70029254

*/

心路历程（本题真实 debug 链）

这道题本地样例过、提交却 WA，挖出来是一条挺长的链：

• 层边界右转：最早用 reorder_polygon 对每层重排到"该层最低点"。第一层对，内层错——构造出 n=5 反例 $1(11,9)\,2(1,11)\,3(10,2)\,4(9,8)\,5(5,9)$ ，外层 $\{3,1,2\}$ 描完，内层从自己最低点 $4$ 进，路径 $2\to4\to5$ 在 $4$ 处右转（叉积 $-4$ ）。随机测 4 万组，约 15% 非法（右转 + 自交两种症状）。

• 续接式入口：改成"从上一层前进方向逆时针扫，第一个扫到的内层顶点当入口"（ $\mathrm{ccwAngle}$ 最小），右转和自交都消失。

• 两个实现 bug：(1) 取 argmin 时 mn_angle = angle 写反成 angle = mn_angle ，导致永远选最后一个；(2) rotate 转错容器（转了已拼好的答案 ans ，应该转新层 convex_poly ）。

• 共线层折返：修完上面随机测仍有约 0.7% WA，全是"剩余点共线 → 弱凸包折返出重复点 → 非全排列"。加有向面积判退化后，2 万随机 + 2 千全共线专测 100% 通过。

教训：几何题"本地样例过 $\ne$ 对"，对拍要主动覆盖共线 / 退化 / 多层嵌套形状，光靠样例和近圆形点集测不出来。

附件

下方挂了交互式演示 HTML 本体（下载后改回 .html 用浏览器打开，可一步步点 Step）、几个关键帧截图，以及完整带教对话录 PDF。

reorder_polygon_bug.html.txt

完整带教对话录（PDF 版）