ZigZagK的博客
[几何+思维]Codeforces1477C【Nezzar and Nice Beatmap】题解
ZigZagK
2021年2月6日 10:26
Codeforces
查看标签

题目概述

CF1477C

解题报告

呜呜呜，几何学太差了，根本不会。

三角形大边对大角，所以最小边一定是锐角。

随便选一个点开始走，每次选距离最远的，那么夹角一定是锐角。

示例程序

#include<cstdio>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=5000;

int n;pair<int,int> a[maxn+5];bool vis[maxn+5];

LL sqr(LL x) {return x*x;}
LL Dis(pair<int,int> a,pair<int,int> b) {return sqr(a.fr-b.fr)+sqr(a.sc-b.sc);}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d",&a[i].fr,&a[i].sc);
    putchar('1');vis[1]=true;
    for (int t=1,lst=1;t<n;t++){
        LL MAX=0;int ID=0;
        for (int i=1;i<=n;i++)
            if (!vis[i] && i!=lst && Dis(a[lst],a[i])>MAX) MAX=Dis(a[lst],a[i]),ID=i;
        printf(" %d",ID);lst=ID;vis[ID]=true;
    }
    puts("");return 0;
}
版权声明：本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处！