首页 > 试题广场 >

浇花

[编程题]浇花
  • 热度指数:4968 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

一个花坛中有很多花和两个喷泉。

喷泉可以浇到以自己为中心,半径为r的圆内的所有范围的花。

现在给出这些花的坐标和两个喷泉的坐标,要求你安排两个喷泉浇花的半径r1和r2
使得所有的花都能被浇到的同时, r12 + r22 的值最小。

输入描述:
第一行5个整数n,x1,y1,x2,y2表示花的数量和两个喷泉的坐标。
接下来n行,每行两个整数xi, yi表示第i朵花的坐标。
满足1 <= n <= 2000,花和喷泉的坐标满足-107<= x, y <= 107


输出描述:
一个整数,r12 + r2的最小值。
示例1

输入

2 -1 0 5 3
0 2
5 2

输出

6
public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] line1 = bf.readLine().split(" ");
        int n = Integer.parseInt(line1[0]);
        int x1 = Integer.parseInt(line1[1]);
        int y1 = Integer.parseInt(line1[2]);
        int x2 = Integer.parseInt(line1[3]);
        int y2 = Integer.parseInt(line1[4]);
        long[][] dis = new long[n][2];
        for (int i = 0; i < n; i++) {
            String[] pos = bf.readLine().split(" ");
            /**
             * 这里不转成 long 类型的话,后面再计算距离时候会出现整数溢出,导致我的通过率一直是20%
             */
            long x = Integer.parseInt(pos[0]);
            long y = Integer.parseInt(pos[1]);
            dis[i][0] = ((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y));
            dis[i][1] = ((x2 - x) * (x2 - x) + (y2 - y) * (y2 - y));
        }
        //根据到喷泉(x1,y1)的距离从大到小进行排序
        Arrays.sort(dis, (a, b) -> b[0] > a[0] ? 1 : -1);
        long ret = Long.MAX_VALUE, d2 = 0;
        /**
         *  当 i = 0,时候,即视为将所有的点归为第一个喷泉,所以 ret = dis[i][0] + 0,每次保存到喷泉2的最大距离,
         *  当 n = i时候,表示前面第 0~i 个点都归为喷泉1,后面i+1~n个点都归为喷泉2,那我们只要记录i+1~n中喷泉2的最大
         *  半径即可,最后需要注意特殊情况,当n个点全部归为喷泉2的情况,即结果要在ret和d2中取最小值
         */
        for (int i = 0; i < n; i++) {
            ret = Math.min(ret, dis[i][0] + d2);
            d2 = Math.max(d2, dis[i][1]);
        }
        System.out.println(Math.min(ret, d2));
    }
}







发表于 2019-08-09 13:41:34 回复(0)

时间复杂度n^2
按距离其中一个点排序
再找另一个的最大值

n,x1,y1,x2,y2 = map(int, input().split())
flowers = []
for i in range(n):
    x,y = map(int, input().split())
    flowers.append((x,y))
l1,l2 = [], []
l = []
for x,y in flowers:
    distance1 = (x1 - x) ** 2 + (y1 - y) ** 2
    distance2 = (x2 - x) ** 2 + (y2 - y) ** 2
    l.append([distance1, distance2])
l = sorted(l, key=lambda x:x[0])
l.insert(0,[0,0])
l.append([0,0])
res = float("inf")
for i in range(len(l)-1):
    res = min(res, l[i][0] + max(l[i+1:], key=lambda x:x[1])[1])
print(res)
编辑于 2019-08-23 10:14:39 回复(0)
先将所有的花按照与第一个喷泉的距离升序排列,然后假设第一个喷泉最远可以浇到第i朵花,那在这种情况下,遍历第二个喷泉要浇到剩下所有花的半径应该是多大。遍历i的情况和第二个喷泉要浇到剩下的花的情况,计算出最小的半径平方和即可。
n, x1, y1, x2, y2 = map(int, input().split())
pos = []
for _ in range(n):
    pos.append(list(map(int, input().split())))
# 先将所有花按与第一个喷泉的距离排序
pos.sort(key=lambda p: (p[0] - x1)**2 + (p[1] - y1)**2)
min_value = float("inf")
# 如果第一个喷泉最远能浇到距离它第i远的花,那要浇到其他的花需要第二个喷泉至少有多大射程
for i in range(-1, n):
    if i < 0:
        # 第一个喷泉一朵都浇不到
        r1 = 0
    else:
        r1 = (pos[i][0] - x1)**2 + (pos[i][1] - y1)**2
    # 遍历所有的可能性
    r2 = 0
    for j in range(i + 1, n):
        r2 = max(r2, (pos[j][0] - x2)**2 + (pos[j][1] - y2)**2)
    min_value = min(min_value, r1 + r2)
print(min_value)


发表于 2021-02-26 22:47:56 回复(0)
cqz头像 cqz
如果数据只过了60%可以看看这篇博客
发表于 2020-03-31 11:58:17 回复(0)
// 抛砖引玉,如果去掉排序,时间复杂度应该是 O(n)
let [num, xa, ya, xb, yb] = readline().split(' ').map(e => e*1), tempX, tempY, dist;
const arrayA=[], arrayB=[];

for(let i=0; i<num; ++i){
    [tempX, tempY] = readline().split(' ').map(e => e*1);
    dist = Math.pow(Math.abs(tempX-xa), 2) + Math.pow(Math.abs(tempY-ya), 2);
    arrayA.push([tempX, tempY, dist]);
}

arrayA.sort((a, b) => a[2] - b[2]);

for(let i=arrayA.length; i>=0; --i){
    if(i === arrayA.length) arrayB[i] = 0;
    else{
        dist = Math.pow(Math.abs(arrayA[i][0]-xb), 2) + Math.pow(Math.abs(arrayA[i][1]-yb), 2);
        arrayB[i] = dist > arrayB[i+1] ? dist : arrayB[i+1];
    }
}

arrayA[-1] = [0, 0, 0];
let min = Number.POSITIVE_INFINITY;

for(let i=-1; i<num; ++i){
    dist = arrayA[i][2] + arrayB[i+1];
    min = min > dist ? dist : min;
}

print(min);

发表于 2020-03-14 12:29:35 回复(0)
O(n^2) 固定一个点,这里要先排序
对花到点A的距离排序,排序后设A的最大距离浇到第i多花,遍历B要覆盖其他所有花的距离,记录一下结果就可以了
n,x1,y1,x2,y2 = [int(x) for x in input().split()]
res = 0x3f3f3f3f3f3f3f3f
data = []
for i in range(n):
    data.append([int(x) for x in input().split()])
data.sort(key = lambda x:(x[0]-x1)**2+(x[1]-y1)**2)
for i in range(-1,n):
    if i==-1:
        cur_d1 = 0
    else:
        cur_d1 = (data[i][0]-x1)**2+ (data[i][1]-y1)**2
    cur_d2 = 0
    for j in range(i+1,n):
        cur_d2 = max(cur_d2,(data[j][0]-x2)**2+(data[j][1]-y2)**2)
    res = min(res,cur_d1+cur_d2)
print(res)


发表于 2019-11-29 22:59:43 回复(0)
#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll Dist(ll x1, ll y1, ll x2, ll y2) {
	return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

struct node{
	ll x, y;
}a[2020];
int mark[2020];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	ll x1, y1, x2, y2;
	ll r1 = 0, r2 = 0;
	ll Min = (ll)1e18 + 10;
	cin >> n >> x1 >> y1 >> x2 >> y2;
	for (int i = 0; i < n; i++) {
		cin >> a[i].x >> a[i].y;
	}
	for (int i = 0; i < n; i++) {
		memset(mark, 0, sizeof(mark));
		r1 = 0;
		r2 = 0;
		r1 = Dist(x1, y1, a[i].x, a[i].y);
		mark[i] = 1;
		for (int j = 0; j < n; j++) {
			if (mark[j]) continue;
			if (Dist(x1, y1, a[j].x, a[j].y) <= r1) {
				mark[j] = 1;
			}
		}
		for (int j = 0; j < n; j++) {
			if (mark[j]) continue;
			r2 = max(r2, Dist(x2, y2, a[j].x, a[j].y));
		}
		Min = min(Min, r1 + r2);
	}
	ll Max = 0;
	for (int i = 0; i < n; i++) {
		Max = max(Max, Dist(x2, y2, a[i].x, a[i].y));
	}
	Min = min(Min, Max);
	Max = 0;
	for (int i = 0; i < n; i++) {
		memset(mark, 0, sizeof(mark));
		r1 = 0;
		r2 = 0;
		r2 = Dist(x2, y2, a[i].x, a[i].y);
		mark[i] = 1;
		for (int j = 0; j < n; j++) {
			if (mark[j]) continue;
			if (Dist(x2, y2, a[j].x, a[j].y) <= r2) {
				mark[j] = 1;
			}
		}
		for (int j = 0; j < n; j++) {
			if (mark[j]) continue;
			r1 = max(r1, Dist(x1, y1, a[j].x, a[j].y));
		}

		Min = min(Min, r1 + r2);
	}
	for (int i = 0; i < n; i++) {
		Max = max(Max, Dist(x1, y1, a[i].x, a[i].y));
	}
	Min = min(Min, Max);
	cout << Min << "\n";
	return 0;
}

发表于 2019-11-29 14:11:33 回复(0)
对于所有花组成的集合,记为F,喷泉1、喷泉2覆盖到的花的集合记为F1、F2,显然F1和F2的并集必须等于F,即所有的花必须至少被一个喷泉覆盖。
若一个数组存储了F,这个数组根据喷泉1的距离由近及远来排序,那么,假设我们指定了喷泉1的喷出距离r1,这个数组具有这样一个划分:距离喷泉1小于等于r1的花在数组的左边、距离大于r1的花占据数组的右边。显然这个划分左边的所有元素组成的集合就是F1,即距离小于等于r1的花被喷泉1覆盖,大于r1的则没有被喷泉1覆盖。F2同理。
所以就可以得到这样一个算法:两个数组都存储花的位置,但分别以距离由近到远对喷泉1和喷泉2排序,尝试数组1所有的划分,同时在保证F1和F2的并集为F的前提下尽可能地使数组2的划分靠左(因为这样r1^2 + r2^2可以在此时尽可能地小),取所有划分中r1^2 + r2^2中的最小值作为最终的结果。
代码如下,复杂度O(n * log n)
#include <bits/stdc++.h>
#define N 2005
using namespace std;
typedef pair<int, int> PII;
typedef long long int64;
 
PII f1[N], f2[N];
 
struct PII_hash {
    size_t operator()(const PII& p) const {
        return hash<int64>()((int64(p.first) << 32) | p.second);
    }
};
struct Cmp {
    int x, y;
    int64 disSq(const PII& p) const {
        int64 u = p.first - x, v = p.second - y;
        return u * u + v * v;
    }
    bool operator()(const PII& a, const PII& b) const {
        return disSq(a) < disSq(b);
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    int n;
    Cmp to1, to2;
    cin >> n >> to1.x >> to1.y >> to2.x >> to2.y;
    for (int i = 0; i < n; ++i) cin>>f1[i].first>>f1[i].second;
    memcpy(f2 + 1, f1, n * sizeof f1[0]);
    f2[0] = PII(to2.x, to2.y);
    sort(f1, f1 + n, to1);//两个数组分别以对喷泉1和喷泉2的距离平方排序
    sort(f2, f2 + n + 1, to2);
    int64 ans = to2.disSq(f2[n]);
    unordered_set<PII, PII_hash> covered;
    for (int i = 0, j = n; i < n; ++i) {
        covered.insert(f1[i]);
        //在一一尝试数组1的划分的同时使数组2的划分尽可能靠左
        while (j > 0 && covered.count(f2[j])) j--;
        ans = min(ans, to1.disSq(f1[i]) + to2.disSq(f2[j]));
    }
    cout << ans << '\n';
}

编辑于 2019-05-05 18:53:45 回复(1)
不排序只比较,但是结果只通过了70%,求大神解释那30%是个啥
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc =new Scanner(System.in);
        int n =sc.nextInt();
        long x1=sc.nextLong(),y1=sc.nextLong();
        long x2=sc.nextLong(),y2=sc.nextLong();
        long max1=0,max2=0;
        for(int i=0;i<n;i++){
            long x0=sc.nextLong();
            long y0=sc.nextLong();
            long dis1 = (x0-x1)*(x0-x1)+(y0-y1)*(y0-y1);
            long dis2 = (x0-x2)*(x0-x2)+(y0-y2)*(y0-y2);
            if(dis1>max1 && dis2>max2){
                if(dis1+max2<dis2+max1)
                    max1=dis1;
                else
                    max2=dis2;
            }
        }
        System.out.println(max1+max2);
    }
}
发表于 2020-03-28 15:11:45 回复(0)
	//计算每朵花到两个喷泉的距离
	int calDistance(int x, int y, int flow_x, int flow_y) {
		return pow(x - flow_x, 2) + pow(y - flow_y, 2);
	}

	//排序函数,从小到大
	bool static cmp_wf(pair<long, long> pos1, pair<long, long> pos2) {
		if (pos1.first == pos2.first)
		{
			return pos1.second < pos2.second;
		}
		return pos1.first < pos2.first;
	}

	void wateringFlowers() {
		int n, x1, y1, x2, y2;
		//花朵数量,两个喷泉坐标值
		cin >> n >> x1 >> y1 >> x2 >> y2;
		//vector<pair<int, int>> flower(n);
		int flow_x, flow_y;
		long dis1, dis2;
		//每朵花到两个喷泉的距离数组
		vector<pair<long, long>> dis(n);
		//接收花朵坐标值
		for (int i = 0; i < n; i++)
		{
			cin >> flow_x >> flow_y;
			dis1 = calDistance(x1, y1, flow_x, flow_y);
			dis2 = calDistance(x2, y2, flow_x, flow_y);
			dis[i].first = dis1;
			dis[i].second = dis2;
		}
		//考虑喷泉距离为0的情况,为距离数组首添加 (0, 0)
		dis.insert(dis.begin(), make_pair<long, long>(0, 0));
		//排序
		sort(dis.begin(), dis.end(), cmp_wf);
		//尾部插入(0, 0)
		dis.push_back(make_pair<long, long>(0, 0));
		//
		long res = INT_MAX, r1 = 0, r2 = 0;
		for (int i = 0; i < n+1; i++)
		{
			r1 = 0;
			//第1个喷泉到 第[0, i]朵花的最大距离
			for (int j = 0; j <= i; j++)
			{
				r1 = max(r1, dis[j].first);

			}
			r2 = 0;
			//第2个喷泉到 第[i+1, n]朵花的最大距离
			for (int k = i+1; k < n+2; k++)
			{
				r2 = max(r2, dis[k].second);
			}
			//r1 = max(dis[0].first, dis[i].first);
			//r2 = max(dis[i+1].second, dis[n+1].second);
			res = min(res, r1 + r2);
		}
		cout << res << endl;
	}

求大佬看看为啥AC=20%?
发表于 2020-05-30 12:33:24 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int x1 = in.nextInt();
        int y1 = in.nextInt();
        int x2 = in.nextInt();
        int y2 = in.nextInt();
        long[][] flowers = new long[n][2];
        for (int i = 0; i < n; i ++) {
            flowers[i][0] = in.nextLong();
            flowers[i][1] = in.nextLong();
        }
        TreeMap<Long, Long> map = new TreeMap<>();
        for (long[] f : flowers) {
            long key = (f[0] - x1) * (f[0] - x1) + (f[1] - y1) * (f[1] - y1);
            long val = (f[0] - x2) * (f[0] - x2) + (f[1] - y2) * (f[1] - y2);
            map.put(key, val);
        }
        long rOne = map.lastKey();
        long rTwo = 0;
        long res = rOne + rTwo;
        while (!map.isEmpty()) {
            rTwo = Math.max(map.pollLastEntry().getValue(), rTwo);
            rOne = map.isEmpty() ? 0 : map.lastKey();
            if (res >= rOne + rTwo) {
                res = rOne + rTwo;
            }
        }
        System.out.println(res);
    }
}
用 TreeMap 的实现

发表于 2020-03-21 19:03:24 回复(0)
求大神解答 为啥只有80%:
不通过
您的代码已保存
答案错误:您提交的程序没有通过所有的测试用例
case通过率为80.00%
用例:
4 0 0 5 0
9 4
8 3
-1 0
1 4
对应输出应该为:
33
你的输出为:
36
a=list(map(int,input().split()))
r1=[]
r2=[]
r3=[]
r4=[]
for i in range(a[0]):
    x,y=map(int,input().split())
    r3.append((x-a[1])**2+(y-a[2])**2)
    r4.append((x-a[3])**2+(y-a[4])**2)
    if (x-a[1])**2+(y-a[2])**2>=(x-a[3])**2+(y-a[4])**2:
        r2.append((x-a[3])**2+(y-a[4])**2)
    else:
        r1.append((x-a[1])**2+(y-a[2])**2)
print(min(max(r1)+max(r2),max(r3),max(r4)))


编辑于 2019-08-17 16:21:27 回复(0)
import sys
def dir(a1,b1,a2,b2):
    return (a2-a1)**2+(b2-b1)**2
def ma2(index,lst):
    ma = 0
    for i in range(index+1,len(lst)):
        ma = max(lst[i][1],ma)
    return ma
def ma1(index,lst):
    ma = 0
    for i in range(index+1,len(lst)):
        ma = max(lst[i][0],ma)
    return ma
num,x1,y1,x2,y2 = map(int,input().split())
lst = []
for i in range(num):
    t1,t2 = map(int,input().split())
    lst.append([dir(x1,y1,t1,t2),dir(x2,y2,t1,t2)])
lst.sort(key = lambda x:(x[0]))
res = sys.maxsize
for i in range(len(lst)):
    res = min(lst[i][0]+ma2(i,lst),res)
lst.sort(key = lambda x:(x[1]))
for i in range(len(lst)):
    res = min(lst[i][1]+ma1(i,lst),res)
print(res)

发表于 2019-05-06 11:10:12 回复(0)