【Codeforces Round 340 (Div 2)C】【暴力排序枚举】Watering Flowers 2个灌溉器灌溉所有点最小的rr+RR

本文主要是介绍【Codeforces Round 340 (Div 2)C】【暴力排序枚举】Watering Flowers 2个灌溉器灌溉所有点最小的rr+RR,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

C. Watering Flowers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A flowerbed has many flowers and two fountains.

You can adjust the water pressure and set any values r1(r1 ≥ 0) and r2(r2 ≥ 0), giving the distances at which the water is spread from the first and second fountain respectively. You have to set such r1 and r2 that all the flowers are watered, that is, for each flower, the distance between the flower and the first fountain doesn't exceed r1, or the distance to the second fountain doesn't exceed r2. It's OK if some flowers are watered by both fountains.

You need to decrease the amount of water you need, that is set such r1 and r2 that all the flowers are watered and the r12 + r22 is minimum possible. Find this minimum value.

Input

The first line of the input contains integers nx1y1x2y2 (1 ≤ n ≤ 2000 - 107 ≤ x1, y1, x2, y2 ≤ 107) — the number of flowers, the coordinates of the first and the second fountain.

Next follow n lines. The i-th of these lines contains integers xi and yi ( - 107 ≤ xi, yi ≤ 107) — the coordinates of thei-th flower.

It is guaranteed that all n + 2 points in the input are distinct.

Output

Print the minimum possible value r12 + r22. Note, that in this problem optimal answer is always integer.

Examples
input
2 -1 0 5 3
0 2
5 2
output
6
input
4 0 0 5 0
9 4
8 3
-1 0
1 4
output
33
Note

The first sample is (r12 = 5r22 = 1):The second sample is (r12 = 1r22 = 32):

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 2020, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int n;
LL X1, Y1, X2, Y2;
LL x[N], y[N];
LL K(LL x) { return x*x; }
LL check(LL r)
{r = r*r;LL R=0;for (int i = 1; i <= n; ++i){if (K(x[i] - X1) + K(y[i] - Y1) <= r);else{gmax(R, K(x[i] - X2) + K(y[i] - Y2));}}return r+R;
}
struct A
{LL x, y, d, D;bool operator < (const A& b)const {return d < b.d;}
}a[N];
int main()
{while (~scanf("%d", &n)){scanf("%lld%lld%lld%lld", &X1,&Y1,&X2,&Y2);for (int i = 1; i <= n; ++i){scanf("%lld%lld", &a[i].x, &a[i].y);a[i].d = K(a[i].x - X1) + K(a[i].y - Y1);a[i].D = K(a[i].x - X2) + K(a[i].y - Y2);}sort(a + 1, a + n + 1); a[0].d = 0;LL ans = 1e18;for (int i = 0; i <= n; ++i){LL R = 0;for (int j = i + 1; j <= n; ++j)gmax(R, a[j].D);gmin(ans, a[i].d + R);}printf("%lld\n", ans);}return 0;
}
/*
【trick&&吐槽】
最近做题太不认真了,这题我竟然没怎么想清楚就写了三分。
写完才发现样例都跑不出。实在是太蠢了!
三分是错误的。
因为在r位于[a[p].d a[p+1].d]范围内时,可能当r为两侧(a[p].d a[p+1].d)的权值时更优。
不满足整体单峰性。【题意】
有2个灌溉器,坐标分别在(X1,Y1)和(X2,Y2)
有n个点需要被灌溉,给出你坐标。
问你,我们如何设置这2个灌溉器的灌溉半径r与R,才能使得所有的点都被灌溉到。
且r^2+R^2尽可能小。【类型】
暴力排序枚举 or 三分【分析】
很显然,r和R都是恰好灌溉到距离其最远的点就好了。
然而,这不意味着r和R是整数。
只意味着r^2与R^2是整数。我们发现点数n很小,只有2000
于是自然想到,我们可以暴力。
如果我们把每个点到1号灌溉源距离的平方设为d,到2号灌溉源距离的平方设为D
那么,我们枚举r^2,只要把所有的d排成升序依次枚举即可。
剩下的灌溉不到的,让2号灌溉源处理。【时间复杂度&&优化】
O(n^2)*/


这篇关于【Codeforces Round 340 (Div 2)C】【暴力排序枚举】Watering Flowers 2个灌溉器灌溉所有点最小的rr+RR的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/610437

相关文章

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》:本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较:二、开始比较总结概要公司存在多

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi

通过C#获取PDF中指定文本或所有文本的字体信息

《通过C#获取PDF中指定文本或所有文本的字体信息》在设计和出版行业中,字体的选择和使用对最终作品的质量有着重要影响,然而,有时我们可能会遇到包含未知字体的PDF文件,这使得我们无法准确地复制或修改文... 目录引言C# 获取PDF中指定文本的字体信息C# 获取PDF文档中用到的所有字体信息引言在设计和出

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序