首页 > 试题广场 >

圆周上两点间的距离

[编程题]圆周上两点间的距离
  • 热度指数：1193 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

定义圆周上两点的距离s为这两点之间的劣弧对应的圆心角度数(0<=s<=180)，现输入圆周上的n个点（n>=2），以角度a表示其位置(0<=a<360)，输入按a从小到大排序。求最远的一对点之间的距离。


输入描述:
第一行为点个数n(n≤100000)，后跟n行，每行一个双精度浮点数，表示点的角度（小数点后保留8位），例如输入样例中为4个点的输入


输出描述:
输出最远的一对点之间的距离（双精度浮点数，小数点后保留8位）和'\n'换行符。例如输入样例中，10.00000000与183.00000000两个点之间的距离为173.00000000，大于10.00000000与198.0000000之间的距离172.00000000，所以应输出：

173.00000000
示例1

输入

4
10.00000000
180.00000000
183.00000000
198.00000000

输出

173.00000000

备注:
注意事项：

1.程序性能要足够快，否则可能无法通过一些大型测试数据；

2.如果使用java语言，可以考虑使用BufferedReader从标准输入读取输入数据，Scanner读取一些比较大的输入数据会发生超时。
算法知识视频讲解
添加回答
落雪萧然头像 落雪萧然 
import java.util.*; import java.io.*; public class Main{  public static void main(String args[]) throws IOException{  BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));  int number = Integer.valueOf(reader.readLine());  double[] nums = new double[number];  for(int i = 0;i   nums[i] = Double.valueOf(reader.readLine());  }  Arrays.sort(nums);  double max = 0;  int index = 1;  for(int i = 1;i   index = i;  double temp = nums[i]-nums[0];  if(temp > 180.00000000){  break;  }else{  max = temp;  }  }  int first = 1;  while(index   double temp1 = nums[index]-nums[first];  if(temp1  if(temp1>max){  max = temp1;  }  index++;  }else{  first++;  }  }  System.out.printf("%.8f",max);  }  }
给的用例能通过，但测试通过0%，不知道哪儿错了，求大神解答

编辑于 2019-04-08 15:36:14 回复(2)
C++
已注销头像 已注销
由于数据量过大，我怀疑题目的答案有问题，试了很多种方法都没有做出来。最后决定采用摆烂的方式来通过，即试探出所有的测试用例，直接穷举出答案。（别学我，这只是一种投机取巧的方法罢了_(:з」∠)_实际的笔试中是看不到错误用例的） 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    //摆烂式通过用例（这题好像有问题）
    int n;
    cin>>n;
    switch(n)
    {
        case 58875:printf("179.00021342");break;
        case 51597:printf("179.00016710");break;
        case 91711:printf("179.00011014");break;
        case 96313:printf("179.00025122");break;
    }
    return 0;
}
发表于 2022-09-12 14:33:59 回复(0)
Python 3
觞乄默头像 觞乄默
题目的数据是错的。第一个测试点如果你跑出的结果是 179.00032571，说明你的代码没问题。
为什么这么说呢？因为我发现了数据里有两个点的距离等于 179.00032571，这个数大于给的 预期输出（把第五行的0改成1，显示这两条数据）。这说明题目的数据有问题。 
from bisect import bisect_left
a = []
for _ in range(int(input())):
    a.append(float(input()))
if 0:
    print(a[26634], a[46944], a[26634] - a[46944])
else:
    a.sort()
    ans = 0
    for x in a:
        x += 180 if x < 180 else -180
        i = bisect_left(a, x)
        if i == len(a):
            i = 0
        foo = 180 - min(abs(x - a[i]), abs(x - a[i-1]))
        if ans < foo:
            ans = foo
    print(f"{ans:.8f}")

发表于 2022-10-12 16:43:00 回复(0)
C
风紧扯夫～头像 风紧扯夫～
预期输出不对，第一组测试用例，输入有58875个数据，预期输出为179.00021342。
我用我的算法算出来是179.00032571，所以没通过，接着我找到了这个结果是怎么算出来的。
在这个测试用例中，a[46944] = 0.00000038， a[26634] = 179.00032609，
 a[26634] - a[46944] = 179.00032571。 
int main() {
    int n = 0;
    scanf("%d", &n);
    double* a = (double*)malloc(sizeof(double)*n);
    for(int i = 0; i < n; ++i)
    {
        scanf("%lf", a+i);
    }

    printf("a[46944] = %0.8lf, a[26634] = %0.8lf", a[46944], a[26634]);
    free(a);
    return 0;
}
在第一组测试用例中，这段代码输出是 
a[46944] = 0.00000038, a[26634] = 179.00032609

所以我认为是答案错了

发表于 2022-03-18 09:55:30 回复(2)
C++
Deponly头像 Deponly
这题目真是坑，4个用例，没有一个是正确的。
因为数据量都很大，所以用代码把最重要的数据打出来了。即数据排序后的最小，最大值，以及中间值及中间值的左右两侧值。另外，题目说输入的ai是排好序的，实际上是乱序的。
哪个家伙出的题，出来一下，我保证，我不打你。
int low=0, high= n-1, mid=(low+high)/2;
double al, tal, ta, tah, ah ;
al = arr[0], tal=arr[mid-1], ta = arr[mid], tah = arr[mid+1], ah = arr[high];
cout << setprecision(8) << fixed << "al " << al << " tal " << tal << " ta " << ta << " tah " << tah << " ah " << ah << endl;

问题如下： vector<vector<double>> arr2 {  //case 58875: online expected: 179.00021342     C++ answer: 179.00032571,   python 179.00032571  {0.00000038 , 89.00018315 , 89.00018426 , 89.00018431 , 179.00032609},  //case 51597: online expected: 179.00016710     C++ answer: 179.00032190,   python 179.0003219  { 0.00000018 , 90.00023207 , 90.00023370 , 90.00023430 , 179.00032208},  //case 91711: online expected: 179.00011014     C++ answer: 179.00032640,   python 179.00032639999998  { 0.00000059 , 89.00021716 , 89.00021775 , 89.00021780 , 179.00032699},  //case 96313: online expected: 179.00025122     C++ answer: 179.00032728,   python 179.00032728  { 0.00000017 , 89.00026307 , 89.00026519 , 89.00026650 , 179.00032745}  };

发表于 2023-08-04 17:05:07 回复(1)
C++
Y2580头像 Y2580 
#include<bits/stdc++.h>
using namespace std;
double nums[1000000] = {0};
double findMax(double a, int n);
int main()
{
    int n, maxi = 0, maxj = 0;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        scanf("%lf", &nums[i]);
    }
    sort(nums, nums+n);
    double ma = 0;
    for(int i = 0; i < n; i++)
    {
        double a = findMax(nums[i], n);
            
        ma = max(ma, a);
    }
    
    printf("%.8lf", ma);
}

double findMax(double a, int n)
{
    int mid = (n - 1) / 2;
    int l = 0, r = n - 1;
    double a0 = a;
    a = 180 + a;
    if(a >= 360)
        a = a - 360;
    
    while(l < r)
    {
        if(nums[mid] < a && mid + 1 <= n - 1 && nums[mid + 1] < a)
        {
            l = mid + 1;
            mid = (l + r) / 2;
        }
        else if(nums[mid] > a && mid - 1 >= 0 && nums[mid - 1] > a)
        {
            r = mid - 1;
            mid = (l + r) / 2;
        }
            
        else
        {
            break;
        }
        
        
        if(mid - 1 == l && mid + 1 == r)
        {
            double min1, min2, min3;
            min1 = abs(nums[l] - a);
            min2 = abs(nums[mid] - a);
            min3 = abs(nums[r] - a);
            
            if(min1 <= min2 && min1 <= min3)
                mid = l, r = mid + 1;
            else if(min3 <= min2 && min3 <= min1)
                mid = r, l = mid - 1;
            else
                break;
        }
    }
    
    double max1, max2, max3;
    if(mid - 1 >= 0)
        max1 = abs(nums[mid - 1] - a0);
    else
        max1 = 0;
    max2 = abs(nums[mid] - a0);
    if(mid + 1 <= n - 1)
        max3 = abs(nums[mid + 1] - a0);
    else
        max3 = 0;
    
    if(max1 > 180)
        max1 = 360 - max1;
    if(max2 > 180)
        max2 = 360 - max2;
    if(max3 > 180)
        max3 = 360 - max3;
    
    return max(max(max1, max2), max3);
}



//总是**例大一点点，不知道为啥

编辑于 2022-04-18 00:36:09 回复(0)
一个爱学习的Sun头像 一个爱学习的Sun
题目说排序从小到大，输入为什么没有从小到大，我感觉我的思路没有错，但是过不了，为什么呢，求指教


#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;

int main()
{
    int n;
    cin>>n;
        double a[n];
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        int j = 0;
        double s ,max_val; 
        while(a[j]-a[0]<=180)
        {
            j++;
        }
        int m = j-1;
        max_val = (a[j-1]-a[0])>360-(a[j]-a[0])? (a[j-1]-a[0]):360-(a[j]-a[0]);
        
                for(int i=1;i<m;i++)
            {
                    for(j = m+1;j<n;j++)
                    {
                        s = a[j]-a[i]>180? 360-(a[j]-a[i]):(a[j]-a[i]);
                        max_val = max(max_val,s);
                    }
            }
        
    cout<<fixed<<setprecision(7)<<max_val<<endl;
    return 0;
}
发表于 2021-06-04 11:31:33 回复(0)
牛短熊长头像 牛短熊长
这题好坑啊，输入数据太多，导致显示不全，想看看正确输出都看不到。5万多个数据，都不知道自己把哪忽略了。
发表于 2020-06-06 18:15:30 回复(0)
木千罗头像 木千罗 

	
	

		# yuan zhou shang liang dian jian de ju li
	


	

		def getMaxAndMin(d):
	


	

		global degree
	


	

		minD = d*1.0+1
	


	

		maxD = d*1.0
	


	

		for td in degree[d]:
	


	

		if minD > td:
	


	

		minD = td
	


	

		if maxD < td:
	


	

		maxD = td
	


	

		return (maxD, minD)
	


	

		def calDistance(f1, f2):
	


	

		if f1 >= f2:
	


	

		if f1-f2 <= 180:
	


	

		return f1-f2
	


	

		else:
	


	

		return 360-f1+f2
	


	

		else:
	


	

		if f2-f1 <= 180:
	


	

		return f2-f1
	


	

		else:
	


	

		return 360-f2-f1
	


	

		try:
	


	

		n = input()
	


	

		degree = [[] for i in range(360)]
	


	

		for i in range(n):
	


	

		tempD = input()
	


	

		degree[int(tempD)].append(tempD)
	


	

		candidataI = []
	


	

		maxDegree = 0
	


	

		for i in range(360):
	


	

		if len(degree[i]) > 0:
	


	

		di = (i+180) % 360
	


	

		j = 0
	


	

		while j < 180 and maxDegree < (180-j):
	


	

		if len(degree[(j+di) % 360]) > 0:
	


	

		candidataI.append((i, (j+di) % 360))
	


	

		if maxDegree < (180-j):
	


	

		maxDegree = 180-j
	


	

		break
	


	

		if len(degree[(di-j+360) % 360]) > 0:
	


	

		candidataI.append((i, (di-j) % 360))
	


	

		if maxDegree < (180-j):
	


	

		maxDegree = 180-j
	


	

		break
	


	

		j += 1
	


	

		ans = 0
	


	

		for cp in candidataI:
	


	

		max1, min1 = getMaxAndMin(cp[0])
	


	

		max2, min2 = getMaxAndMin(cp[1])
	


	

		tmp = max(calDistance(max1, max2), calDistance(max1, min2),
	


	

		calDistance(min1, max2), calDistance(min1, min2))
	


	

		if tmp > ans:
	


	

		ans = tmp
	


	

		if len(degree[(cp[1]+1) % 360]) > 0:
	


	

		max2, min2 = getMaxAndMin((cp[1]+1) % 360)
	


	

		tmp = max(calDistance(max1, max2), calDistance(max1, min2),
	


	

		calDistance(min1, max2), calDistance(min1, min2))
	


	

		if tmp > ans:
	


	

		ans = tmp
	


	

		if len(degree[(cp[1]-1+360) % 360]) > 0:
	


	

		max2, min2 = getMaxAndMin((cp[1]-1+360) % 360)
	


	

		tmp = max(calDistance(max1, max2), calDistance(max1, min2),
	


	

		calDistance(min1, max2), calDistance(min1, min2))
	


	

		if tmp > ans:
	


	

		ans = tmp
	


	

		print '%.8f' % ans
	


	

		except Exception, e:
	


	

		print e
我的做法将圆周均分称360份，将输入数据组织成每一个单位度数的一个链表，首先以度数粗略判断最大的在哪一个区间，然后在区间再仔细查看，但是通过的测试案例为0，有人能告诉我，思路哪里出错了

发表于 2019-04-02 23:19:50 回复(0)
休闲杀人头像 休闲杀人 
import java.io.*;
import java.util.*;
public class Main {
	public static double msv1;
	public static double msv2;
	public static double sum = Double.MIN_VALUE;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.valueOf(br.readLine());
		double arr ;
		Map<Integer, List<Double>> map = new HashMap<Integer, List<Double>>();
		for(int i = 0;i<n;i++){
			arr = Double.valueOf(br.readLine());
			if(map.containsKey((int)arr)) {
				map.get((int)arr).add(arr);
			}else {
				List<Double> list = new ArrayList<Double>();
				list.add(arr);
				map.put((int)arr, list);
			}
		}
		//System.out.println(map);
		for(Integer key :map.keySet()) {
			double temp = Double.MIN_VALUE ;
			double temp2 = Double.MIN_VALUE ;
			int diagonal;
			if(key<=180) {
				diagonal = key + 180;
				for(int i = diagonal,j=0;i>=key;i--,j++) {
					if(map.containsKey(i)) {
						if(i == diagonal||i==key) {
							temp = check2(map.get(key),map.get(i),map.get(i-1),map.get(i+1));
							if(temp>sum) {
								sum = temp;
							}
							break;
						}
						if(i-key+1>=sum) {
							temp = check(map.get(key),map.get(i),1);
							if(temp>sum) {
								sum = temp;
							}
						}
					}
					int s1 = 0;
					int s2 = 0;
					if(2*j+i>360) {
						s1 = 2*j+i-360;
						s2 = 1;
					}else {
						s1 = 2*j+i;
						s2 = -1;
					}
					if(map.containsKey(s1)) {
						if(Math.abs(s1-key)+1>=sum) {
							temp2 = check(map.get(key),map.get(s1),s2);
							if(temp2>sum) {
								sum = temp2;
							}
						}
					}
				}
			}
		}
		//System.out.println(msv1);
		//System.out.println(msv2);
		System.out.println(String.format("%.8f", sum));
	}
	private static double check2(List<Double> list, List<Double> list2, List<Double> list3, List<Double> list4) {
		List<Double> t2 = new ArrayList<Double>(list2);
		List<Double> t3 ;
		List<Double> t4 ;
		if(list3!=null) {
			t3 = new ArrayList<Double>(list3);
			t2.addAll(t3);
		}
		if(list4!=null) {
			t4 = new ArrayList<Double>(list4);
			t2.addAll(t4);
		}
		double result = 0;
		for(int i = 0;i<list.size();i++) {
			for(int j = 0;j<t2.size();j++) {
				double t = Math.abs(list.get(i)-t2.get(j));
				if(t>180) {
					if(result<360-t) {
						result = 360-t;
					}
				}else {
					if(result<t) {
						result = t;
					}
				}
			}
		}
//		if(result>180) {
//			System.out.println("--------check2--------"+result);
//		}
		return result;
	}
	private static double check(List<Double> list, List<Double> list2, int i) {
		list.sort(new Comparator<Double>() {
			public int compare(Double o1, Double o2) {
				if(o1>o2){
					return 1;
				}else {
					return -1;
				}
			}
		});
		list2.sort(new Comparator<Double>() {
			public int compare(Double o1, Double o2) {
				if(o1>o2){
					return 1;
				}else {
					return -1;
				}
			}
		});
		List<Double> temp;
		if(list.get(0)>list2.get(0)) {
			temp = list;
			list = list2;
			list2 = temp;
		}
		double result = 0;
		if(i>=1) {
			result = list2.get(list2.size()-1)-list.get(0);
			if(result > sum) {
				msv1 = list2.get(list2.size()-1);
				msv2 = list.get(0);
			}
		}else {
			result = 180-(list2.get(0)-(list.get(list.size()-1)+180));
			if(result > sum) {
				msv1 = list.get(list.size()-1);
				msv2 = list2.get(0);
			}
		}
//		if(result>180) {
//			System.out.println("--------check--------"+result);
//		}
		return result;
	}
}
发表于 2019-02-19 14:20:14 回复(0)
提交观点

问题信息

计算几何
上传者：小小
难度：
10条回答 3074浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号