搜狗2018校招在线考试-编程题

发表于 | 分类于 ，

题目

描述

在一个圆上选定任意一点为原点 O,
圆上任意一点的坐标为此点与原点 O 的顺时针夹角,
即任意点的坐标区间为[0,360),
定义两个点之间的距离为两点之间与圆心形成的最大圆心劣角的大小,
现在给出 n 个圆上的点,求出这些点之间的最大距离,
且保留至小数点后 8 位

输入

n+1 行,
第 1 行 n 为点的个数
第 2 行到第 n+1 行为每个点的坐标

输出

1 行,这些点之间的最大距离

Example

Input

4
10.00000000
180.00000000
183.00000000
198.00000000

Output

173.00000000

题解

动态规划

  1. 记录当前开始位置 s,终止位置 e
  2. 初始值 s=0,e=1
  3. 依次增大 e ,计算 s,e 之间的距离 d
  4. 当 s,e 之间的距离小于等于 180 时
    • 用 d 更新最大距离 maxd
    • 向后移动 e
  5. 若大于 180
    • 用 360-d 更新maxd
    • 向后移动 s
  6. 若 e<n-1 重复 3-6 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin>>n;
    double *points=new double[n];
    for(int i=0;i<n;++i)
        cin>>points[i];
    sort(points,points+n);
    int s=0,e=0;
    double d=0,maxd=0;
    while(e<n)
    {
        d=points[e]-points[s];
        if(d<=180)
            maxd=max(maxd,d),++e;
        else
            maxd=max(maxd,360-d),++s;
    }
    cout<<setiosflags(ios::fixed)<<setprecision(8)<<maxd;
}