保护罩

问题描述

假设宇宙射线的发射点位于一个平面，ZJM已经通过特殊手段获取了所有宇宙射线的发射点，他们的坐标都是整数。而ZJM要构造一个保护罩，这个保护罩是一个圆形，中心位于⼀个宇宙射线的发射点上。为了节省经费，需要做一个最⼩⾯积的保护罩。

Input

输⼊第一行一个正整数 n，表示宇宙射线发射点的个数
接下来 N 行，每行两个整数 x,y，表示宇宙射线发射点的位置
n ≤ 1000，|x| ≤ 100000，|y| ≤ 100000

Output

输出包括两行
第一行输出保护罩的中心坐标 x, y，用空格隔开
第二行输出保护罩半径的平方
（所有输出保留两位小数，如有多解，输出 x 较小的点，如扔有多解，输出 y 较小的点）
无行末空格

Sample

Input: 
5
0 0
0 1
1 0
0 -1
-1 0

Output: 
0.00 0.00
1.00

Limitation

Time limit      1000 ms
Memory limit    262144 kb

解题思路

一开始是想成最小圆覆盖问题，有注意到圆心在其中的某个点上，最后还是 WA 了……

然后其实这道题暴力就能解决，对于每个点，求出其他点到这个点的距离，取最大值，即得出这个点能到达的最远点；然后取这些最大值的最小值，就是所求半径。

全部用 double 来处理小数点问题。

源代码

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

struct dot {
	double x, y;
	dot() { x = 0; y = 0; }
	dot(double a, double b) :x(a), y(b) {  }
};

double disBetPow(dot a, dot b) {
	double xx = a.x - b.x;
	double yy = a.y - b.y;
	return (double)(xx * xx + yy * yy);
}

int main() {
	int n;
	cin >> n;
	vector<dot> v;
	while (n--) {
		double x, y;
		cin >> x >> y;
		dot D(x, y);
		v.push_back(D);
	}
	dot O = v[0];
	double dis1 = 0;
	for (int i = 1; i != v.size(); i++)
		dis1 = max(dis1, disBetPow(O, v[i]));
	
	double o_x = O.x, o_y = O.y;
	for (int i = 1; i != v.size(); i++) {
		double dis2 = 0;
		for (int j = 0; j != v.size(); j++)
			dis2 = max(dis2, disBetPow(v[i], v[j]));
		if (dis1 >= dis2) {
			if ((dis2 == dis1 && (v[i].x < o_x || (v[i].x == o_x && v[i].y < o_y)))
				|| dis1 > dis2) {
				o_x = v[i].x;
				o_y = v[i].y;
				dis1 = dis2;
			}
		}
	}
	cout << fixed << setprecision(2);
	cout << o_x << " " << o_y << endl;
	cout << dis1 << endl;

	return 0;
}