zoj 2107 Quoit Design(最近点对问题,好好思考,分治)

2023-11-08 12:08

本文主要是介绍zoj 2107 Quoit Design(最近点对问题,好好思考,分治),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1、http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1107

2、题目大意:

给定n个点的坐标,求出最近两个点的距离的一半

最近点对,可以用分治来做,先按x轴排序,然后每次将平面分成两半,分别求解 ,对于一次合并,先找出离划分线距离小于当前最小值的点,然后将这些点按y轴排序,其实x轴也一样,再暴力求这些点的最近点,每次y坐标的差值大于答案,直接break

3、题目:

Quoit Design

Time Limit: 5 Seconds      Memory Limit: 32768 KB

Have you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.

Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.


Input

The input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.


Output

For each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.


Sample Input

2
0 0
1 1
2
1 1
1 1
3
-1.5 0
0 0
0 1.5
0


Sample Output

0.71
0.00
0.75


4、AC代码:

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 111111
struct node
{double x,y;
}g[N];
int q[N];
int n;
bool cmp(node p,node q)
{return p.x<q.x;
}
bool cmpy(int a,int b)
{return g[a].y<g[b].y;
}
double Dis(node P,node Q)
{return sqrt((P.x-Q.x)*(P.x-Q.x)+(P.y-Q.y)*(P.y-Q.y));
}
double NearPoint(int l,int r)
{if(l>=r)return 1e30;int i,j,n=0,m=(l+r)>>1;double a=min(NearPoint(l,m),NearPoint(m+1,r));for(i=m;i>=l;--i)if(g[m].x-g[i].x<a)q[n++]=i;else break;for(i=m+1;i<=r;++i)if(g[i].x-g[m].x<a)q[n++]=i;else break;sort(q,q+n,cmpy);for(i=0;i<n;++i)for(j=i+1;j<n;++j)if(g[q[j]].y-g[q[i]].y<a)a=min(a,Dis(g[q[i]],g[q[j]]));else break;return a;
}
int main()
{while(scanf("%d",&n),n){for(int i=0;i<n;++i)scanf("%lf%lf",&g[i].x,&g[i].y);sort(g,g+n,cmp);printf("%.2lf\n",NearPoint(0,n-1)/2);}return 0;
}



这篇关于zoj 2107 Quoit Design(最近点对问题,好好思考,分治)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Flask解决指定端口无法生效问题

《Flask解决指定端口无法生效问题》文章讲述了在使用PyCharm开发Flask应用时,启动地址与手动指定的IP端口不一致的问题,通过修改PyCharm的运行配置,将Flask项目的运行模式从Fla... 目录android问题重现解决方案问题重现手动指定的IP端口是app.run(host='0.0.

Seata之分布式事务问题及解决方案

《Seata之分布式事务问题及解决方案》:本文主要介绍Seata之分布式事务问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Seata–分布式事务解决方案简介同类产品对比环境搭建1.微服务2.SQL3.seata-server4.微服务配置事务模式1

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》:本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

Spring MVC跨域问题及解决

《SpringMVC跨域问题及解决》:本文主要介绍SpringMVC跨域问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录跨域问题不同的域同源策略解决方法1.CORS2.jsONP3.局部解决方案4.全局解决方法总结跨域问题不同的域协议、域名、端口

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

基于.NET编写工具类解决JSON乱码问题

《基于.NET编写工具类解决JSON乱码问题》在开发过程中,我们经常会遇到JSON数据处理的问题,尤其是在数据传输和解析过程中,很容易出现编码错误导致的乱码问题,下面我们就来编写一个.NET工具类来解... 目录问题背景核心原理工具类实现使用示例总结在开发过程中,我们经常会遇到jsON数据处理的问题,尤其是

springboot3.4和mybatis plus的版本问题的解决

《springboot3.4和mybatisplus的版本问题的解决》本文主要介绍了springboot3.4和mybatisplus的版本问题的解决,主要由于SpringBoot3.4与MyBat... 报错1:spring-boot-starter/3.4.0/spring-boot-starter-

在 Spring Boot 中使用异步线程时的 HttpServletRequest 复用问题记录

《在SpringBoot中使用异步线程时的HttpServletRequest复用问题记录》文章讨论了在SpringBoot中使用异步线程时,由于HttpServletRequest复用导致... 目录一、问题描述:异步线程操作导致请求复用时 Cookie 解析失败1. 场景背景2. 问题根源二、问题详细分

解读为什么@Autowired在属性上被警告,在setter方法上不被警告问题

《解读为什么@Autowired在属性上被警告,在setter方法上不被警告问题》在Spring开发中,@Autowired注解常用于实现依赖注入,它可以应用于类的属性、构造器或setter方法上,然... 目录1. 为什么 @Autowired 在属性上被警告?1.1 隐式依赖注入1.2 IDE 的警告: