Codeforces

Luogu

分析

首先用 $A_1,A_2$ 两个点将凸包分为两部分。我们容易用 $n-2$ 次询问二求出其它的 $n-2$ 个点在左侧还是右侧。

接着用 $n-2$ 次询问一，求出其他每个点与 $A_1,A_2$ 构成的三角形的面积。这时我们实际上已经得知了每个点到直线 $A_1A_2$ 的距离。

我们把两侧的点分开处理。对于某一侧的点（假设已按逆时针排列），显然它们到 $A_1A_2$ 的距离是单峰的。因此我们可以先找出该侧的最大值，然后就得知了该侧的峰。我们把这个点记为 $A_{mid}$。

接着，我们仅需要用询问二求出该侧所有点在直线 $A_1A_{mid}$ 的左侧还是右侧即可。

这样子我们可以得到四段弧上的点，其中每段弧内部的顺序可以排序解决。总询问次数为 $\mathcal{O}(3n-8)$。

代码

代码一开始求的是顺时针顺序，所以可读性可能比较差 /kel

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int cmp(pair<ll,int> a,pair<ll,int> b) { return b<a; }
inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;

int n; ll S[N]; int sgn[N];
vector<pair<ll,int> > L,R,LL,LR,RL,RR;

int main() {
    n=read();
    for (re int i=3;i<=n;++i) {
        printf("1 1 2 %d\n",i),fflush(stdout); S[i]=read();
        printf("2 1 2 %d\n",i),fflush(stdout); sgn[i]=read();
        if (sgn[i]>0) L.push_back(make_pair(S[i],i));
        else R.push_back(make_pair(S[i],i));
    }
    sort(L.begin(),L.end()),sort(R.begin(),R.end());
    for (re int i=3;i<=n;++i) {
        if (sgn[i]>0) {
            if (i==L.back().second) continue;
            printf("2 1 %d %d\n",L.back().second,i),fflush(stdout);
            if (read()>0) LL.push_back(make_pair(S[i],i));
            else LR.push_back(make_pair(S[i],i));
        } else {
            if (i==R.back().second) continue;
            printf("2 1 %d %d\n",R.back().second,i),fflush(stdout);
            if (read()>0) RL.push_back(make_pair(S[i],i));
            else RR.push_back(make_pair(S[i],i));
        }
    }
    sort(LL.begin(),LL.end(),cmp),sort(LR.begin(),LR.end());
    sort(RL.begin(),RL.end(),cmp),sort(RR.begin(),RR.end());
    printf("0 1 ");
    for (re auto i:RR) printf("%d ",i.second);
    if (!R.empty()) printf("%d ",R.back().second);
    for (re auto i:RL) printf("%d ",i.second);
    printf("2 ");
    for (re auto i:LR) printf("%d ",i.second);
    if (!L.empty()) printf("%d ",L.back().second);
    for (re auto i:LL) printf("%d ",i.second);
    puts(""); fflush(stdout);
    return 0;
}