【Google Code Jam 2009 round2 problem D】Watering Plants (两圆交点求法详解)

本文主要是介绍【Google Code Jam 2009 round2 problem D】Watering Plants (两圆交点求法详解),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【Google Code Jam 2009 round2 problem D】Watering Plants 

你在温室种植了N株植物。为了给这些植物浇水,你购买了2台自动浇水的机器。每株植物i的圆心为(Xi,Yi),半径为Ri。任意两个圆都不相交或相切。每台机器都可以给某个完全包含于半径为r的圆形区域内的植物浇水。求最小的r使得存在一种方案能给所有植物浇水。

限制条件

1<=Xi<=1000

1<=Yi<=1000

1<=Ri<=100

Small

1<=N<=3

Large

1<=N<=40

输入

2
3
20 10 2
20 20 2
40 10 3
3
20 10 3
30 10 3
40 10 3

输出

Case #1: 7.000000
Case #2: 8.000000


分析:

0)该题在《挑战程序竞赛第二版》【1】3.7.4中有所介绍,给出了求解算法,误差分析和临界情况的示例,本文整理了其中的思路并添加了产生临界情况的详细分析和求两圆交点坐标公式的推导

1)若对半径r存在一种浇水方案,则对任意R>r,对半径R肯定也存在一种浇水方案。因此容易想到可以使用二分搜索的方法在解空间搜索满足条件的最小值。

2)现在的问题在于能否找到一种高效的判别算法C(r)判断对半径r是否存在一种浇水方案。当两个浇水器的半径确定时,可以放置的位置有无数种情况,但是我们只需要判断两浇水器处于临界位置时是否存在浇水方案(即2个半径为r的圆是否刚好能覆盖所有植物)。当两个圆半径最小时,由于植物数N>=3,两个圆覆盖的植物数N1,N2>=1,若一个圆覆盖的植物数为1,则它半径最小时必定正好与它覆盖的植物同心。若一个圆覆盖的植物数Ni>=2,则它一定至少与两个植物相切。因此两个圆的圆心存在两种临界位置。求出所有临界位置的圆的圆心(这样的圆共有O(n^2)个)。判断这些临界位置的圆中是否存在两个圆可以覆盖所有的植物。因此存在复杂度为O(n^2)的判断算法

3)求解和两植物相切的浇水器的圆心

设植物圆1的圆心为O1(X1,Y1),半径为r1,植物圆2的圆心为O2(X2,Y2),半径为r2,浇水器半径为R

由于浇水器与植物1,2都相切,浇水器圆心在以O1为圆心,R1=R-r1为半径的圆和以O2为圆心,R2=R-r2为半径的圆的交点处。因此我们需要求解两圆交点的坐标。

设存在两圆X,Y

圆X 圆心A(x,y),半径R1, 圆Y的圆心B(a,b),半径R2,两圆交点为C、D,CD与AB的交点为E,过C作平行于Y轴直线,过E作平行于X轴直线,两者相较于F,过B作平行于Y轴直线,过A作平行X轴直线,两者相交于G,设E坐标为(x0,y0),FE=x4,CF=y4,如下图【2】所示



令dx=a-x dy=b-y  a=AB=sqrt((a-b)^2+(b-y)^2)

CE^2=AC^2-AE^2=BC^2-BE^2=BC^2-(AB-AE)^2

整理得AE=(R1^2-R2^2+a^2)/(2a)

易得x0=dx*AE/AB

令b=AE/AB=(R1^2-R2^2+a^2)/(2a^2)

则x0=dx*b

同理y0=dy*b

易得三角形CFE与三角形AGB相似,因此

FE/CE=BG/AB

CE^2=AC^2-AE^2=R1^2-(b*a)^2

FE=BG/AB*CE=dy/a*sqrt(R1^2-(b*a)^2)=dy*sqrt(R1^2/a^2-b^2)

令d=sqrt(R1^2/a^2-b^2)

则x4=FE=dy*d

同理y4=CF=dy*d

于是

C点坐标为(x0-x4,y0+y4)

D点坐标为(x0+x4,y0-y4)

Q.E.D 

4)代码可以参考【1】中的实现

参考资料

【1】《挑战程序设计竞赛》作者秋叶拓哉 / 岩田阳一/北川宜稔 

【2】图片来自于《两圆相交求交点算法证明》 

http://wenku.baidu.com/link?url=hlnh_qEKfbTg1tEcLLHeLUdhfL_5px9sEj2aLPSmVSjuqdwNIAaM46iSzWX-L3srkdY1LnNJBsUJCwQyZklh3cPasuA1TLLOsmdL2D6GEkm

这篇关于【Google Code Jam 2009 round2 problem D】Watering Plants (两圆交点求法详解)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MySQL 8 中的一个强大功能 JSON_TABLE示例详解

《MySQL8中的一个强大功能JSON_TABLE示例详解》JSON_TABLE是MySQL8中引入的一个强大功能,它允许用户将JSON数据转换为关系表格式,从而可以更方便地在SQL查询中处理J... 目录基本语法示例示例查询解释应用场景不适用场景1. ‌jsON 数据结构过于复杂或动态变化‌2. ‌性能要

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

Python 字典 (Dictionary)使用详解

《Python字典(Dictionary)使用详解》字典是python中最重要,最常用的数据结构之一,它提供了高效的键值对存储和查找能力,:本文主要介绍Python字典(Dictionary)... 目录字典1.基本特性2.创建字典3.访问元素4.修改字典5.删除元素6.字典遍历7.字典的高级特性默认字典

MySQL 主从复制部署及验证(示例详解)

《MySQL主从复制部署及验证(示例详解)》本文介绍MySQL主从复制部署步骤及学校管理数据库创建脚本,包含表结构设计、示例数据插入和查询语句,用于验证主从同步功能,感兴趣的朋友一起看看吧... 目录mysql 主从复制部署指南部署步骤1.环境准备2. 主服务器配置3. 创建复制用户4. 获取主服务器状态5

一文详解如何使用Java获取PDF页面信息

《一文详解如何使用Java获取PDF页面信息》了解PDF页面属性是我们在处理文档、内容提取、打印设置或页面重组等任务时不可或缺的一环,下面我们就来看看如何使用Java语言获取这些信息吧... 目录引言一、安装和引入PDF处理库引入依赖二、获取 PDF 页数三、获取页面尺寸(宽高)四、获取页面旋转角度五、判断

Spring Boot中的路径变量示例详解

《SpringBoot中的路径变量示例详解》SpringBoot中PathVariable通过@PathVariable注解实现URL参数与方法参数绑定,支持多参数接收、类型转换、可选参数、默认值及... 目录一. 基本用法与参数映射1.路径定义2.参数绑定&nhttp://www.chinasem.cnbs

MySql基本查询之表的增删查改+聚合函数案例详解

《MySql基本查询之表的增删查改+聚合函数案例详解》本文详解SQL的CURD操作INSERT用于数据插入(单行/多行及冲突处理),SELECT实现数据检索(列选择、条件过滤、排序分页),UPDATE... 目录一、Create1.1 单行数据 + 全列插入1.2 多行数据 + 指定列插入1.3 插入否则更

Redis中Stream详解及应用小结

《Redis中Stream详解及应用小结》RedisStreams是Redis5.0引入的新功能,提供了一种类似于传统消息队列的机制,但具有更高的灵活性和可扩展性,本文给大家介绍Redis中Strea... 目录1. Redis Stream 概述2. Redis Stream 的基本操作2.1. XADD