链接

CF1477C

题解

现场得分：过了

我现场的做法

• 我用了一个调整法，这个方法在随机数据下跑得飞快，最差也只有\(O(n^2)\)。
• 我们考虑当前的点的序列为\(\{A_n\}\)。
• 假设当前我们发现最前面的一个非锐角的地方是\(A_{i-2},A_{i-1},A_i\)（记这个角为\(B_{i-2}\)），则我们如果仅想让这一个点变好，不考虑其他地方，可以直接将序列变成\(A'=...,A_{i-1},A_{i-2},A_{i}\)。根据三角形的性质，我们可以知道这一定是调整成功了的。
• 但是，有可能导致这里调整好了，\(A_{i-3},A_{i-2},A_i\)这个角不行了。
• 一个朴素的想法是我们调整完\(B_{i-2}\)之后，往前移一步，看看\(B_{i-3}\)行不行。行的话就继续往后，不行就按上述方法调整\(B_{i-3}\)，并再往前看一步。
• 而这样子调整可以保证调整\(B_{i-3}\)时，不会对\(B_{i-2}\)产生影响。
• 所以如果\(B_1,...,B_{i-3}\)合法，\(B_{i-2}\)不合法，在调整不超过\(i-2\)次之后就一定会使局面变成\(B_1,...,B_{i-2}\)合法。
• 所以这个东西的最多调整次数为\(\frac{(n-2)(n-1)}{2}=O(n^2)\)。而事实上调整数字会远远小于他。

另外的做法

• 一开始随便选择一个点作为起始。
• 每次选定距离序列尾部的点最远的点，放入序列尾部。
• 可以利用大角对大边证明这件事一定是对的。

代码

#include<bits/stdc++.h>
#define LL long long
#define MAXN 5010
using namespace std;
template<typename T> void Read(T &cn)
{
	char c; int sig = 1;
	while(!isdigit(c = getchar())) if(c == '-') sig = 0;
	if(sig) {cn = c-48; while(isdigit(c = getchar())) cn = cn*10+c-48; }
	else    {cn = 48-c; while(isdigit(c = getchar())) cn = cn*10+48-c; }
}
template<typename T> void Write(T cn)
{
	int wei = 0; T cm = 0; int cx = cn%10; cn/=10;
	if(cn < 0 || cx < 0) {putchar('-'); cn = 0-cn; cx = 0-cx; }
	while(cn)cm = cm*10+cn%10,cn/=10,wei++;
	while(wei--)putchar(cm%10+48),cm/=10;
	putchar(cx+48);
}
template<typename T> void WriteL(T cn) {Write(cn); puts(""); }
template<typename T> void WriteS(T cn) {Write(cn); putchar(' '); }
template<typename T> void Max(T &cn, T cm) {cn = cn < cm ? cm : cn; }
template<typename T> void Min(T &cn, T cm) {cn = cn < cm ? cn : cm; }
struct qwe{
	LL x,y;
	void getit() {Read(x); Read(y); }
	inline friend qwe operator -(qwe cn, qwe cm) {qwe guo; guo.x = cn.x-cm.x; guo.y = cn.y-cm.y; return guo; }
};
LL dianji(qwe cn, qwe cm) {return cn.x*cm.x + cn.y*cm.y; }
qwe a[MAXN+1];
int n;
int xu[MAXN+1];
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	Read(n);
	for(int i = 1;i<=n;i++) a[i].getit(), xu[i] = i;
	int cnt = 0;
	for(int i = 3;i<=n;)
	{
		cnt++;
		if(dianji(a[xu[i]]-a[xu[i-1]], a[xu[i-2]]-a[xu[i-1]]) <= 0) {
			swap(xu[i-2], xu[i-1]); 
			i--; Max(i,3);
		}
		else i++;
		if(cnt >= 100000000) {puts("-1"); return 0; }
//		printf("i = %d cnt = %d %lld\n",i,cnt);
//		for(int j = 1;j<=n;j++) printf("xu[%d] = %d ",j,xu[j]); puts("");
	}
	for(int i = 1;i<=n;i++) WriteS(xu[i]); puts("");
	return 0;
}