vijos 1237 隐形的翅膀

隐形的翅膀

背景

小杉终于进入了天堂。他看到每个人都带着一双隐形翅膀，他也想要。

（小杉是怎么看到的？……）

描述

天使告诉小杉，每只翅膀都有长度，两只翅膀的长度之比越接近黄金分割比例，就越完美。

现在天使给了小杉N只翅膀，小杉想挑出一对最完美的。

格式

输入格式

每组测试数据的
第一行有一个数N(2<=N<=30000)
第二行有N个不超过1e5的正整数，表示N只翅膀的长度。

20%的数据N<=100

输出格式

对每组测试数据输出两个整数，表示小杉挑选出来的一对翅膀。

注意，比较短的在前，如果有多对翅膀的完美程度一样，请输出最小的一对。

样例1

样例输入1

4

2 3 4 6

样例输出1

2

3

限制

每个测试点1s

提示

你可以认为黄金分割比就是0.6180339887498949

来源

lolanv

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 30010

using namespace std;

const long double plase=0.6180339887498949;

int n;

long double ansl,ansr,minn;

long double length[MAXN];

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        cin>>length[i];

    minn=0x7f7f7f7f;

    sort(length+,length++n);

    for(int i=;i<=n;i++){

        long double x=length[i]/plase;

        int mid=lower_bound(length+i,length+n+,x)-length;

        x=length[i]/length[mid]-plase;

        long double k=fabs(x);

        if(k<minn){

            minn=k;

            ansl=length[i];

            ansr=length[mid];

        }

        x=length[i]/length[mid-];k=fabs(x-plase);

        if(k<minn){

            minn=k;

            ansl=length[i];

            ansr=length[mid-];

        }

    }

    printf("%d\n%d",int(ansl),int(ansr));

}

/*

3

4 5 6 7 8

*/