【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

相关文章

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.对单个变量进行排序

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

Java 枚举的常用技巧汇总

《Java枚举的常用技巧汇总》在Java中,枚举类型是一种特殊的数据类型,允许定义一组固定的常量,默认情况下,toString方法返回枚举常量的名称,本文提供了一个完整的代码示例,展示了如何在Jav... 目录一、枚举的基本概念1. 什么是枚举?2. 基本枚举示例3. 枚举的优势二、枚举的高级用法1. 枚举

Rust中的Option枚举快速入门教程

《Rust中的Option枚举快速入门教程》Rust中的Option枚举用于表示可能不存在的值,提供了多种方法来处理这些值,避免了空指针异常,文章介绍了Option的定义、常见方法、使用场景以及注意事... 目录引言Option介绍Option的常见方法Option使用场景场景一:函数返回可能不存在的值场景