最小圆覆盖

vc白萝卜

输入n个点的坐标，n<500, 求半径最小的圆能覆盖这n个点，在圆周上也算覆盖。
输出圆心坐标和半径的100倍的整数部分（不要四拾伍入）

输入格式
第一行一个整数n
接着n行，每行一个点的坐标，两个整数，中间一个空格
重复输入直至n=0

输出格式
每行一个结果，最小圆的X坐标的100倍整数部分、Y坐标的100倍整数部分、半径的100倍整数部分。
每行都有回车，n=0的除外

例子：
输入：
3
0 0
1 0
1 1
4
5 3
3 3
5 0
0 2
5
0 1
1 0
2 1
3 2
4 1
0

输出：
50 50 70
270 150 274
200 100 200
有大神会吗，这些语言都可以 C/C++  DEV C++ python java c# 求救！！！

老八秘制

@heidern0612
你希望得到问题解决的心情我们可以理解，但是你确实没必要重复发帖
导致不必要的问题，严重了就被封号
希望新手能看看版规

xiaosi4081

你把你前两个发的删了，不然别人会扣你分

liuzhengyuan

这些语言都可以 C/C++  DEV C++ python java c#

难不成 DEV C++ 是一门语言？

heidern0612

老八秘制 发表于 2020-5-14 15:48
@heidern0612
你希望得到问题解决的心情我们可以理解，但是你确实没必要重复发帖
导致不必要的问题，严 ...

嗯，新人，大度一点吧。

sunrise085

作为一个论坛提问，程序代码量挺大的
需要用到一定的算法
写了一下，但是没有写任何容错措施。运行时，一定要按照你所说的格式进行输入

1. import math
   
2. def get_center(point1,point2,point3):#求三点的外接圆的圆心坐标
   
3.     a = point2[0] - point1[0]
   
4.     b = point2[1] - point1[1]
   
5.     c = point3[0] - point2[0]
   
6.     d = point3[1] - point2[1]
   
7.     e = point2[0]**2 + point2[1]**2 - point1[0]**2 - point1[1]**2
   
8.     f = point3[0]**2 + point3[1]**2 - point2[0]**2 - point2[1]**2
   
9.     x = (f*b-e*d)/(c*b-a*d)/2;
   
10.     y = (a*f-e*c)/(a*d-b*c)/2;
    
11.     return (x,y)
    
12. 
    
13. def get_result(points):#求多点的最小覆盖圆的半径和圆心坐标
    
14.     center = points[0]
    
15.     rad = 0
    
16.    
    
17.     def d(point1,point2):
    
18.         return math.sqrt((point1[0]-point2[0])**2+(point1[1]-point2[1])**2)
    
19.    
    
20.     for i in range(len(points)):
    
21.         if d(points[i],center)>rad:
    
22.             center = points[i]
    
23.             rad = 0
    
24.             for j in range(i):
    
25.                 if d(points[j],center)>rad:
    
26.                     center = ((points[i][0]+points[j][0])/2,(points[i][1]+points[j][1])/2)
    
27.                     rad = d(points[i],points[j])/2
    
28.                     for k in range(j):
    
29.                         if d(points[k],center)>rad:
    
30.                             center = get_center(points[i],points[j],points[k])
    
31.                             rad = d(points[i],center)
    
32.     return (center,rad)
    
33. 
    
34. result=[]
    
35. while True:#循环获取输入，并计算
    
36.     n = int(input("请输入坐标点数（输入0退出）："))
    
37.     if n == 0:
    
38.         break
    
39.     points = []
    
40.     des = []
    
41.     max_d = (0,0,0)
    
42.     for i in range(n):#输入n个坐标点
    
43.         x , y = (eval(k) for k in input("输入第%d个点的坐标"%(i+1)).split())
    
44.         points.append((x,y))
    
45.    
    
46.     center,rad=get_result(points)#计算n个点的最小覆盖圆
    
47.     result.append((int(center[0]*100),int(center[1]*100),int(rad*100)))#将结果扩大100倍并取整
    
48. for each in result:#循环输出结果
    
49.     print(each[0],each[1],each[2],sep=' ')

复制代码