st0 dxm，yht 的没听了（
CF938F - Erasing Substrings
CF995C - Leaving the Bar
考虑归纳，试图合并两个向量使得 (n) 减少 (1)。
考虑如果直接合并随意的两个向量。那么最差的情况就是两个向量是垂直的，这时候斜边大于直角边。如果两个边相等都等于 (a) 的话，那么合并出来的长度就是 (sqrt2a)。很显然，把 (10^6) 乘两遍 (sqrt2) 你就没掉了。总之这种 naive 的方法是不行的。况且归纳本来就要求除了规模缩小之外，其他条件都不变，而这里显然可能将值域扩大。
注意到两个向量的长度固定了之后，影响他们的和的长度的只有它们的夹角。先不严谨地设它们长度相等，都等于 (x)。那么考虑到等边三角形，显然有它们的和的长度 (leq x) 当且仅当夹角 (alphaleq 60^circ)。但是有可能它们的长度不相等，这时候我们需要证明一下 (xleq) 较长边。
其实并不难证明。如图，(oldsymbol a=overrightarrow{OP}) 为第一个向量（较大），分别以 (O,P) 为圆心，(OP) 为半径作圆。那么第二个向量 (oldsymbol b) 显然为 (O) 与 (OQ,OQ',OQ'') 上任意一点的连线，其中 (OQ,OQ',OQ'') 分别为夹角 (<,=,> 60^circ) 的三种情况。那么 (|oldsymbol a+oldsymbol b|leq |oldsymbol a|) 显然当且仅当该夹角 (alpha) 下的 (OQ) 完全在圆 (P) 内，肉眼可见 (alphaleq 60^circ)。
有了这个结论就不难想到做法了。我们找任意三条向量，它们中夹角最小的一对的夹角显然要 (leqdfrac{360^circ}6=60^circ)，那么每次可以选择这组向量合并来归纳。到最后还剩 (n=2) 的时候，不能保证能找到这组向量了，不过这是无所谓了，乘个 (sqrt2) 恰好增长不到 (1.5) 倍。
接下来考虑实现细节：
- 我不会算向量夹角，不过无伤大雅。只需要每次找到所有可能合成的向量中最短的那个即可。
- 如何合并？需要做的操作是将当前一个向量取反，而任意时刻一个向量可能是多个原向量的化合物，暴力取反大概会炸。考虑到每次恰好合并两个，那就建一棵二叉树，合并用虚拟节点连接两个根，打标记（就是树上差分），最后 DFS 一遍即可。一开始觉得很奇怪，但后来发现和 official solution 重合？然后发现其实还可以无脑启发式。
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define X first
#define Y second
#define pb push_back
#define ppb pop_back
const double inf=1e14;
const int N=100000;
int n;
pair<int,int> a[2*N+1];
int son[2*N+1][2],prod[2*N+1][2];
vector<int> v;
pair<int,int> operator+(pair<int,int> x,pair<int,int> y){return mp(x.X+y.X,x.Y+y.Y);}
pair<int,int> operator*(int x,pair<int,int> y){return mp(x*y.X,x*y.Y);}
pair<int,int> operator-(pair<int,int> x,pair<int,int> y){return x+(-1)*y;}
double len(pair<int,int> x){return sqrt(1ll*x.X*x.X+1ll*x.Y*x.Y);}
int ans[N+1];
void dfs(int x=2*n-1,int now=1){
if(x>n){
dfs(son[x][0],now*prod[x][0]);
dfs(son[x][1],now*prod[x][1]);
}
else ans[x]=now;
}
int main(){
cin>>n;
if(n==1)return puts("1"),0;
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].X,&a[i].Y),v.pb(i);
for(int i=1;i<=n-2;i++){
int x=v.back();v.ppb();
int y=v.back();v.ppb();
int z=v.back();v.ppb();
pair<double,pair<pair<int,int>,pair<int,int> > > mn;
mn.X=inf;
mn=min(mn,mp(len(a[x]+a[y]),mp(mp(x,1),mp(y,1))));
mn=min(mn,mp(len(a[x]-a[y]),mp(mp(x,1),mp(y,-1))));
mn=min(mn,mp(len(a[x]+a[z]),mp(mp(x,1),mp(z,1))));
mn=min(mn,mp(len(a[x]-a[z]),mp(mp(x,1),mp(z,-1))));
mn=min(mn,mp(len(a[y]+a[z]),mp(mp(y,1),mp(z,1))));
mn=min(mn,mp(len(a[y]-a[z]),mp(mp(y,1),mp(z,-1))));
a[i+n]=mn.Y.X.Y*a[mn.Y.X.X]+mn.Y.Y.Y*a[mn.Y.Y.X];
son[i+n][0]=mn.Y.X.X,prod[i+n][0]=mn.Y.X.Y;
son[i+n][1]=mn.Y.Y.X,prod[i+n][1]=mn.Y.Y.Y;
v.pb(i+n);
if(son[i+n][0]==x&&son[i+n][1]==y)v.pb(z);
if(son[i+n][0]==x&&son[i+n][1]==z)v.pb(y);
if(son[i+n][0]==y&&son[i+n][1]==z)v.pb(x);
}
int x=v.back();v.ppb();
int y=v.back();v.ppb();
pair<double,pair<pair<int,int>,pair<int,int> > > mn;
mn.X=inf;
mn=min(mn,mp(len(a[x]+a[y]),mp(mp(x,1),mp(y,1))));
mn=min(mn,mp(len(a[x]-a[y]),mp(mp(x,1),mp(y,-1))));
a[2*n-1]=mn.Y.X.Y*a[mn.Y.X.X]+mn.Y.Y.Y*a[mn.Y.Y.X];
son[2*n-1][0]=mn.Y.X.X,prod[2*n-1][0]=mn.Y.X.Y;
son[2*n-1][1]=mn.Y.Y.X,prod[2*n-1][1]=mn.Y.Y.Y;
dfs();
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}
CF1178H - Stock Exchange
鸽子
CF1109F - Sasha and Algorithm of Silence's Sounds
鸽子
CF960G - Bandit Blues
鸽子
CF1338E - JYPnation
鸽子