Codeforces Round #698 (Div. 1) C Nezzar and Nice Beatmap_codeforces round 698 (div. 1)

题目链接：https://codeforces.com/contest/1477/problem/C

C. Nezzar and Nice Beatmap

time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Nezzar loves the game osu!.

osu! is played on beatmaps, which can be seen as an array consisting of distinct points on a plane. A beatmap is called nice if for any three consecutive points A,B,CA,B,C listed in order, the angle between these three points, centered at BB, is strictly less than 9090 degrees.

 

Points A,B,CA,B,C on the left have angle less than 9090 degrees, so they can be three consecutive points of a nice beatmap; Points A′,B′,C′A′,B′,C′ on the right have angle greater or equal to 9090 degrees, so they cannot be three consecutive points of a nice beatmap.

 

Now Nezzar has a beatmap of nn distinct points A1,A2,…,AnA1,A2,…,An. Nezzar would like to reorder these nn points so that the resulting beatmap is nice.

Formally, you are required to find a permutation p1,p2,…,pnp1,p2,…,pn of integers from 11 to nn, such that beatmap Ap1,Ap2,…,ApnAp1,Ap2,…,Apn is nice. If it is impossible, you should determine it.

Input

The first line contains a single integer nn (3≤n≤50003≤n≤5000).

Then nn lines follow, ii-th of them contains two integers xixi, yiyi (−109≤xi,yi≤109−109≤xi,yi≤109) — coordinates of point AiAi.

It is guaranteed that all points are distinct.

Output

If there is no solution, print −1−1.

Otherwise, print nn integers, representing a valid permutation pp.

If there are multiple possible answers, you can print any.

Example

input

Copy

5
0 0
5 0
4 2
2 1
3 0

output

Copy

1 2 5 3 4

Note

Here is the illustration for the first test:

 

 

Please note that the angle between A1A1, A2A2 and A5A5, centered at A2A2, is treated as 00 degrees. However, angle between A1A1, A5A5 and A2A2, centered at A5A5, is treated as 180180 degrees.

题意：输入$n$个二维点$(3<=n<=5000)$,要求将n个点进行排序，排序后序列中任意相邻的3个点构成的角度为锐角。比如排序后的序列为$A1,A2,.....Ai......An$，对于任意的$(1<i<n)$，$\angle A_{i-1}A_{i}A_{i+1}<90^{\circ}$。

题解：两种方法

第一种：首先任意选择一个点加入序列，然后选择离它最远的点加入序列，这样第三点任意选择一个点构成的角度一定为锐角，我们再选离第二个点最远的点加入队列作为第三个点，以此类推，每次选择离上一个选择的点最远的点加入序列即可。

第二种：由于三角形中，最多只有一个大于等于$90^{\circ}$的角。所以我们任意选择一个点加入序列的结尾，若不满足条件，则和序列的前一个点交换，这样末尾三个点一定满足条件，然后继续判断是否满足条件，不满足条件继续往前交换，直到满足条件为止。

复杂度$O(n^{^{2}})$

代码如下：

第一种方法：

#include<bits/stdc++.h>
 
using namespace std;
const int nn =5100;
const int inff = 0x3fffffff;
const double eps = 1e-8;
typedef long long LL;
const double pi = acos(-1.0);
int n;
LL x[nn],y[nn];
int ans[nn];
bool use[nn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }
    memset(use,false,sizeof(use));
    use[1]=true;
    ans[1]=1;
    for(int i=1;i<n;i++)
    {
        LL maxdis = -1;
        int choose = -1;
        for(int j=1;j<=n;j++)
        {
            if(use[j])
                continue;
            LL dis = (x[j]-x[ans[i]])*(x[j]-x[ans[i]])+(y[j]-y[ans[i]])*(y[j]-y[ans[i]]);
            if(dis > maxdis)
            {
                maxdis = dis;
                choose = j;
            }
        }
        ans[i+1]=choose;
        use[choose]=true;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}

第二种方法：

#include<bits/stdc++.h>
 
using namespace std;
const int nn =5100;
const int inff = 0x3fffffff;
const double eps = 1e-8;
typedef long long LL;
const double pi = acos(-1.0);
const LL mod = (479 << 21) + 1;
int n;
int x[nn],y[nn];
int ans[nn];
bool check(int i,int j,int k)
{
    LL v1x=x[j]-x[i];
    LL v1y=y[j]-y[i];
    LL v2x=x[k]-x[j];
    LL v2y=y[k]-y[j];
    return v1x*v2x+v1y*v2y<0;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }
    ans[1]=1,ans[2]=2;
    for(int i=3;i<=n;i++)
    {
        ans[i]=i;
        for(int j=i;j>=3;j--)
        {
            if(!check(ans[j-2],ans[j-1],ans[j]))
            {
                swap(ans[j],ans[j-1]);
            } else {
                break;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return 0;
}