【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

相关文章

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》:本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

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对数据库设备要求较高)分治法(常