Shy Polygons

Description

You are given two solid polygons and their positions on the xy-plane. You can move one of the two along the x-axis (they can overlap during the move). You cannot move it in other directions. The goal is to place them as compactly as possible, subject to the following condition: the distance between any point in one polygon and any point in the other must not be smaller than a given minimum distance L.
We define the width of a placement as the difference between the maximum and the minimum x-coordinates of all points in the two polygons.
Your job is to write a program to calculate the minimum width of placements satisfying the above condition.
Let's see an example. If the polygons in Figure 13 are placed with L = 10.0, the result will be 100. Figure 14 shows one of the optimal placements.

Input

The input consists of multiple datasets. Each dataset is given in the following format.
L
Polygon1
Polygon2

L is a decimal fraction, which means the required distance of two polygons. L is greater than 0.1 and less than 50.0.
The format of each polygon is as follows.
n
x1 y1
x2 y2
...
xn yn
n is a positive integer, which represents the number of vertices of the polygon. n is greater than 2 and less than 15.
Remaining lines represent the vertices of the polygon. A vertex data line has a pair of nonnegative integers which represent the x- and y-coordinates of a vertex. x- and y-coordinates are separated by a single space, and y-coordinate is immediately followed by a newline. x and y are less than 500.
Edges of the polygon connect vertices given in two adjacent vertex data lines, and vertices given in the last and the first vertex data lines. You may assume that the vertices are given in the counterclockwise order, and the contours of polygons are simple, i.e. they do not cross nor touch themselves.
Also, you may assume that the result is not sensitive to errors. In concrete terms, for a given pair of polygons, the minimum width is a function of the given minimum distance l. Let us denote the function w(l). Then you can assume that |w(L±10-7)-w(L)| < 10-4.
The end of the input is indicated by a line that only contains a zero. It is not a part of a dataset.
Output

The output should consist of a series of lines each containing a single decimal fraction. Each number should indicate the minimum width for the corresponding dataset. The answer should not have an error greater than 0.0001. You may output any number of digits after the decimal point, provided that the above accuracy condition is satisfied.
Sample Input

10.5235
3
0 0
100 100
0 100
4
0 50
20 50
20 80
0 80
10.0
4
120 45
140 35
140 65
120 55
8
0 0
100 0
100 100
0 100
0 55
80 90
80 10
0 45
10.0
3
0 0
1 0
0 1
3
0 100
1 101
0 101
10.0
3
0 0
1 0
0 100
3
0 50
100 50
0 51
0
Sample Output

114.882476
100
1
110.5005

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
DRY原则和Shy原则
保障可维护性的主要诀窍是遵循DRY原则和Shy原则。 在一个系统的整个生命周期里,理解和改动这类维护工作的比例一般非常之高。为了维护的方便,要尽量将系统划分为可以独立理解与改动的模块。这就要在设计的时候注重DRY原则与Shy原则。不过,这两条原则有一定的冲突,并不总能兼得,于是在追求的时候要重视分寸。维护者的两大困扰有两种情况会给维护者增添很大的麻烦:一种是为了调整一个效果,要改动无数个地方;
BZOJ 2821 作诗 (分块)
作诗问题描述 神犇SJY虐完HEOI之后给傻×LYD出了一题: SHY是T国的公主,平时的一大爱好是作诗。 由于时间紧迫,SHY作完诗之后还要虐OI,于是SHY找来一篇长度为N的文章,阅读M次,每次只阅读其中连续的一段[l,r],从这一段中选出一些汉字构成诗。因为SHY喜欢对偶,所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数(两个
2017NOIP模拟赛 D【思维】作诗(分块)
问题描述 神犇SJY虐完HEOI之后给傻×LYD出了一题: SHY是T国的公主,平时的一大爱好是作诗。 由于时间紧迫,SHY作完诗之后还要虐OI,于是SHY找来一篇长度为N的文章,阅读M次,每次只阅读其中连续的一段[l,r],从这一段中选出一些汉字构成诗。因为SHY喜欢对偶,所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数(两个一样的汉字
什么是Excel的快速编号功能?
在办公的上班族们,或许通常有这样的困扰,打开电脑,发现总有遗漏的事情忘记做了,例如忘记给人名加编号了,遇到简单的表格可以自己一个个敲打编号,可是数量多了呢?一个个敲打既消耗时间和精力,还可能出错。不用担心,今天我就以一张“语数外”三科的成绩表为例,来教大家如何快速编号。 1、首先我们看到的是以姓名为第一列的表格,选中A列。 2、单击鼠标右键,在弹出的快捷菜单中,选择“插入”。
【bzoj2821】【作诗】【分块】
Description 神犇SJY虐完HEOI之后给傻×LYD出了一题:SHY是T国的公主,平时的一大爱好是作诗。由于时间紧迫,SHY作完诗 之后还要虐OI,于是SHY找来一篇长度为N的文章,阅读M次,每次只阅读其中连续的一段[l,r],从这一段中选出一 些汉字构成诗。因为SHY喜欢对偶,所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认 为选出的汉字的种
计算几何知识归纳
计算几何知识归纳 目录 ㈠ 点的基本运算 1. 平面上两点之间距离 2. 判断两点是否重合 3. 矢量叉乘 4. 矢量点乘 5. 判断点是否在线段上 6. 求一点饶某点旋转后的坐标 7. 求矢量夹角 ㈡ 线段及直线的基本运算 1. 点与线段的关系 2. 求点到线段所在直线垂线的垂足 3. 点到线段的最近点 4. 点到线段所在直线的距离 5. 点到...
&shy;电子商务“二元”形态之趋势分析&shy;
­电子商务“二元”形态之趋势分析­文/王易见    郎咸平教授有一个著名的“二元经济”理论,即同时存在过热和过冷两种经济形态,不过,“二元”形态不仅仅是经济现象的一个诠释,它更广泛存在于商业经济的各个行业之中。    谈到商业经济,言必称这些年崛起的电子商务,电子商务依靠互联网为平台,有别于传统线下经济,是线上经济的一种重要形态,从这个意义上说,可否将线上经济和线下经济归结于“二
业界技术领域的NURBS 和 POLYGON 工具。
Maya是美国Autodesk公司出品的世界顶级的三维动画软件,应用对象是专业的影视广告,角色动画,电影特技等。
ArcGIS切割多边形以及合并多边形
一、切割   arcgis,arcinfo分割图斑方法在arcgis 环境中将鼠标指向菜单栏,点右键-->选择Editor工具-->start editing-->选择所要编辑的图层-->OK-->使用选择工具,选中所要编辑的图斑-->然后在Editor 工具条的task栏中-->选择Modify tasks-->cut polygon features-->然后使用task旁的编辑工具(铅笔形
POJ 1279 Art Gallery 半平面交+求多边形核的面积
裸的:半平面交+求多边形核的面积 Art Gallery Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 5735   Accepted: 2419 Description The art galleries of the ne
【hdu1632】半平面交模板
Polygons Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 174    Accepted Submission(s): 63 Problem Description Given two convex pol
Programming the Microsoft Windows Driver Model &auml;&cedil;&shy;&aelig;
Programming the Microsoft Windows Driver Model &auml;&cedil;&shy;&aelig;
OpenGL ES 正反面设置指令
OpenGL ES 正反面设置指令
certutil.exe
补充操作系统缺失感染文件!用于Der Spaeher &shy修复
DRY原则和Shy原则 .
保障可维护性的主要诀窍是遵循DRY原则和Shy原则。 在一个系统的整个生命周期里,理解和改动这类维护工作的比例一般非常之高。为了维护的方便,要尽量将系统划分为可以独立理解与改动的模块。这就要在设计的时候注重DRY原则与Shy原则。不过,这两条原则有一定的冲突,并不总能兼得,于是在追求的时候要重视分寸。 维护者的两大困扰 有两种情况会给维护者增添很大的麻烦:一种是为了调整一个效果,要改动无数
shy 的离散性分析
这段代码就是为了设置标签的class属性,对单数行和双数行设置颜色tr id=grN6HG5_tr_{$index} valign=middle>    元素用于向元素添加属性。增加了class属性-->   xsl:attribute name=class>      xsl:choose>        xsl:when test=position()
信息隐藏实验 报告 shy
信息隐藏实验报告 已经作好了 有需要的同志 可以直接下载使用了
系统架构设计之DRY和SHY原则
保障可维护性的主要诀窍是遵循DRY原则和Shy原则。 在一个系统的整个生命周期里,理解和改动这类维护工作的比例一般非常之高。为了维护的方便,要尽量将系统划分为可以独立理解与改动的模块。这就要在设计的时候注重DRY原则与Shy原则。不过,这两条原则有一定的冲突,并不总能兼得,于是在追求的时候要重视分寸。 维护者的两大困扰 有两种情况会给维护者增添很大的麻烦:一种是为了调整一个效果,要改动无数个
2004_Robust Distributed estimation in sensor networks using the embedded polygons algorithm
2004_Robust Distributed estimation in sensor networks using the embedded polygons algorithm
libjpeg.so.62找不到的问题
1. 建立软连接,如下图: 先切换到目录/usr/lib目录下,有一个i386-linux-gnu文件夹。 2、如果还是不行,采用下列解决方案: Step1:sudo apt-get update Step2:sudo apt-get install libjpeg62-dev
pads画多边形copper,总是出现Self-Intersecting Polygon----覆铜成网状
原文地址::http://blog.sina.com.cn/s/blog_66b4d47e0100hp39.html 相关文章 1、用多边形画copper等时总是出现Self-Intersecting Polygon错误提示,解决方法  ----http://yuandi6.blog.163.com/blog/static/207265185201210308252597/
VTK最新帮助文档,很好用CHM 格式的~
VTK最新帮助文档,很好用CHM 格式的~VTK 编程必需资料,分成了三部分了,需要都下载下来方个解压vtk5.1.chm
DRY原则和Shy原则
保障可维护性的主要诀窍是遵循DRY原则和Shy原则。  在一个系统的整个生命周期里,理解和改动这类维护工作的比例一般非常之高。为了维护的方便,要尽量将系统划分为可以独立理解与改动的模块。这就要在设计的时候注重DRY原则与Shy原则。不过,这两条原则有一定的冲突,并不总能兼得,于是在追求的时候要重视分寸。 维护者的两大困扰 有两种情况会给维护者增添很大的麻烦:一种是为了调整一个效果,要改动
Poweriso tool you like
Be good for you ! A beautiful tool in this wed ~ the world will be useing ! the song 'Love the way you like' is very shy ~ right ?
geometry-api-java 学习笔记(五)多边形 Polygons
Polygons API Reference A polygon is defined by a collection of rings. Each ring is a collection of contiguous line segments suchthat the start point and the end point are the same. 看下图,多边形的起点和终
.NET中的DRY和SHY原则
1、定义 DRY原则 DRY——Don't Repeat Yourself。是指在一个项目工程中的东西最好是唯一的,所有东西,包括类,变量,常量,相同的方法,等等。 SHY原则 Shy—害羞,是指各个模块不要把只属于自己的东西公开,从而减少依赖关系,假如出现bug,那么让bug只影响该某块,而不要牵扯整个工程。 2、联系   两个原则都为了增强程序可维护性。但是在某种程度上两个是不能兼
caffe2编译过程中cudnn问题
原本在TX2上已经编译安装好了caffe2,现在想在ubuntu 16.04 desktop 1050Ti编译安装,出现不一样的问题,记录一下 按照caffe2.ai官网说明安装cuda,cudnn等,编译caffe2,出现错误: [ 79%] Linking CXX executable binaries/fully_connected_op_gpu_test libcaffe2_gp
maya中运用displacement map的基本流程
目标:一张灰度图贴到一个平面模型上,产生置换的效果 场景中建立一个polygon平板,放大,在材质编辑器中新建一个lambert材质 在材质编辑器中建立file节点,载入贴图,然后用中键将file节点,连入lambert节点的displacement map 此时需要选择节点,点击材质编辑器上的输入输出按钮,因为displacement贴图的一些参数都在隐藏节点中(也
R|ggplot2 画中国省会地图
小白在实验室打杂 被boss要求画一个省会地图 虽然一开始对R什么都不会,但是整体感觉挺像matlab的 下面写一下我自己作为一个小白遇到的天坑 首先 要先装一个R for windows(我的实验室台机是win10的) 下载R 点击 download 然后我的源是Elite Education 安装时就按默认路径C:\Program Files\R 会给你装一个32位和一个64位的
高级工具smoothPolygon实现的思路
在arcgis工具栏中有smoothPolygon(平滑面)的工具,是将锯齿状的面图层变的更平滑的工具。这个工具在使用的时候输入平滑参数,就可以得到想要的平滑面。平滑过程中,可以选择不同平滑方式,其中一项是将平滑的拓扑错误处理掉的,即可以修正重叠和缝隙。那么这个工具室怎么实现的呢? 首先我调用过smoothPolygon这个gp。smoothPolygon的gp属于高级工具,必须具有AE企业
Realtime lightsourced 720 polygons 3dstudio vector... withou
Realtime lightsourced 720 polygons 3dstudio vector... without directx... using windows standard api’s Tasks
vtk实战(十四)——解析vtk XML 文件的内容
对于vtk XML格式的文件: .vtu, .vtp, .vts, .vtr, .vti, .vto, 解析其存储单元、单元数据。#include <vtkSmartPointer.h> #include <vtkXMLReader.h> #include <vtkXMLUnstructuredGridReader.h> #include <vtkXMLPolyDataReader.h> #incl
运用Polygon类绘制六边形
import javax.swing.JPanel; import java.awt.Graphics; import java.awt.Polygon; public class PolygonsPanel extends JPanel { protected void paintComponent(Graphics g) { super.paintComponent(g); in
摄像头像素和帧数的骗局&shy;
 摄像头像素和帧数的骗局&shy;   2009-11-11 14:35:41|  分类: 技术资料 |  标签: |字号大中小 订阅 60帧120帧和30万插值成1000万像素是同一种骗局­         摄像头从最初的30万像素,被厂家鼓吹到500万,1000万像素,这个卫星放得太高太大了,再往上,消费者都麻木了,一个小小的摄像头,难道说还比数码单反像
Visibility Algorithms In The Plane
Contents Preface page xi 1 Background 1 1.1 Notion of Visibility 1 1.2 Polygon 2 1.3 Asymptotic Complexity 5 1.4 Triangulation 6 1.5 The Art Gallery Problem 8 1.6 Special Types of Visibility 11 2 Point Visibility 13 2.1 Problems and Results 13 2.2 Computing Visibility of a Point in Simple Polygons 16 2.2.1 Non-Winding Polygon: O(n) Algorithm 16 2.2.2 Removing Winding: O(n) Algorithm 23 2.3 Computing Visibility of a Point in Polygons with Holes 31 2.4 Recognizing Simple Polygons Visible from a Point 38 2.5 Notes and Comments 43 3 Weak Visibility and Shortest Paths 46 3.1 Problems and Results 46 3.2 Characterizing Weak Visibility 51 3.3 Computing Weak Visibility in Simple Polygons 58 3.3.1 Scanning the Boundary: O(n log n) Algorithm 58 3.3.2 Using Shortest Path Trees: O(n) Algorithm 65 viii Contents 3.4 Computing Weak Visibility in Polygons with Holes 66 3.5 Recognizing Weakly Internal Visible Polygons 68 3.5.1 Using Visibility Graph: O(E) Algorithm 68 3.5.2 Scanning the Boundary: O(n) Algorithm 73 3.6 Computing Shortest Path Trees 82 3.6.1 In Simple Polygons: O(n) Algorithm 82 3.6.2 In Weak Visibility Polygons: O(n) Algorithm 87 3.7 Recognizing Weakly External Visible Polygons 95 3.8 Notes and Comments 102 4 LR-Visibility and Shortest Paths 105 4.1 Problems and Results 105 4.2 Characterizing LR-Visibility 108 4.3 Computing LR-Visibility Polygons 110 4.4 Recognizing LR-Visibility Polygons 113 4.5 Walking in an LR-Visibility Polygon 115 4.6 Computing Shortest Path Trees using LR-Visibility 124 4.7 Notes and Comments 135 5 Visibility Graphs 136 5.1 Problems and Results 136 5.2 Computing Visibility Graphs of Simple Polygons 138 5.3 Computing Visibility Graphs of Polygons with Holes 143 5.3.1 Worst-Case: O(n2) Algorithm 143 5.3.2 Output-Sensitive: O(n log n + E) Algorithm 146 5.4 Computing Tangent Visibility Graphs 161 5.4.1 Convex Holes: O(n + h2 log h) Algorithm 161 5.4.2 Non-Convex Holes: O(n + h2 log h) Algorithm 165 5.5 Notes and Comments 169 6 Visibility Graph Theory 171 6.1 Problems and Results 171 6.2 Recognizing Visibility Graphs of Simple Polygons 174 6.2.1 Necessary Conditions 174 6.2.2 Testing Necessary Conditions: O(n2) Algorithm 180 6.3 Characterizing Visibility Graphs of Simple Polygons 183 6.4 Recognizing Special Classes of Visibility Graphs 187 6.4.1 Spiral Polygons: O(n) Algorithm 187 6.4.2 Tower Polygons: O(n) Algorithm 195 6.5 Characterizing a Sub-Class of Segment Visibility Graphs 201 6.6 A Few Properties of Vertex-Edge Visibility Graphs 205 6.7 Computing Maximum Clique in a Visibility Graph 208 6.8 Computing Maximum Hidden Vertex Set in a Visibility Graph 214 6.9 Notes and Comments 216 7 Visibility and Link Paths 218 7.1 Problems and Results 218 7.2 Computing Minimum Link Paths in Simple Polygons 221 7.2.1 Using Weak Visibility: O(n) Algorithm 221 7.2.2 Using Complete Visibility: O(n) Algorithm 224 7.3 Computing Minimum Link Paths in Polygons with Holes 231 7.4 Computing Link Center and Radius of Simple Polygons 238 7.5 Computing Minimum Nested Polygons 242 7.5.1 Between Convex Polygons: O(n log k) Algorithm 242 7.5.2 Between Non-Convex Polygons: O(n) Algorithm 248 7.6 Notes and Comments 253 8 Visibility and Path Queries 255 8.1 Problems and Results 255 8.2 Ray-Shooting Queries in Simple Polygons 259 8.3 Visibility Polygon Queries for Points in Polygons 267 8.3.1 Without Holes: O(log n + k) Query Algorithm 267 8.3.2 With Holes: O(n) Query Algorithm 272 8.4 Path Queries Between Points in Simple Polygons 278 8.4.1 Shortest Paths: O(log n + k) Query Algorithm 278 8.4.2 Link Paths: O(log n + k) Query Algorithm 289 8.5 Notes and Comments 292 Bibliography 295 Index 311
unity导入的自定义3D模型从地板掉下去
找了好久,才找到方法 1、导入自定义的3D模型,在project的assets里面 2、选中某个模型,在Inspector视图中,勾选Generate Collider,点击Apply 3、将该模型用到场景中,加刚体属性,执行就不会从地板掉下去了。 这里需要注意的是Mesh Collider这里要勾选Convex,不然还会从地板掉下去,并且会有错误提示:Non-convex
新东方六级英语
  第一课时概述1. 课程安排2. 关于教材3. 课前预习完形填空:1. 完形的阅读量很小2. 完形不涉及很偏很难的词完形是带有明显规律性的考试完形填空的规律和特点:1. 命题思路2. 完形填空的提示线索在文章中的分布规律Passage 7 If a farmer wishes to succeed, he must try to keep
BottomBar类似QQ下面的3个按钮
1.导包        compile 'com.roughike:bottom-bar:2.3.1' 2.创建一个res/xml/bottombar_menu.xml; 3.bottombar_menu.xml里面的代码
Linux +开发板若干问题
一:uboot下 tftp 下载内核 1.开发板和windows能够ping通 保证通过一个网段 windows防火墙关闭 2.windows和linux能够ping通   linux 防火墙关闭 /etc/init.d/iptables stop         setenforce permissive(0) 启动NFS服务器 : service nfs restart 3
A new core-based morphing algorithm for polygons
morphing algorithm 人脸识别
POJ1389Area of Simple Polygons【离散化+线段树+扫描线】
Language: Default Area of Simple Polygons Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 3304   Accepted: 1711 Description There are N, 1 <= N <= 1,000
[Codeforces 166B] Polygons (点在凸多边形内)
Codeforces - 166B 判断任意多边形 B是否严格在凸多边形 A内部 点在凸多边形内部试板题 如果 B的所有顶点在 A内,则 B在 A内 由于 A的顶点有 10510^5个,B的顶点有 10410^4 个 所以不能用 (n)\mathcal{O}(n)的暴力判断 有一个 (logn)\mathcal{O}(logn) 的二分做法 基本原理是用对角线将凸多边形剖成以 co
【codechef】Chef and Polygons(灵活题,坑题)
Input: 1 3 6 -2 2 -1 1 2 2 2 -1 1 -2 -2 -2 3 -1 -1 1 -1 1 1 4 3 3 -3 3 -3 -3 3 -3 Output: 1 0 2 Explanation In the picture the first polygon is marked in green, second - in red and third in b
ArcGIS基本操作收集汇总
arcmap功能操作手册: http://resources.arcgis.com/zh-cn/help/main中文文档说明。 1.1、影像格式的转换 例如把jpg格式转换为tiff格式。可以在arctoolbox中的conversiontools-->to Raster-->Raster to Other Format multiple)。   1.2、矢量化准备。 矢量化前建
使用soft hyphen(&shy;)自动断行
本文的起因是页面中有像“$9.99/yr”这样的字符串,我们希望如果这个字符串太长的话就从“/”前面断开。 最初有两种解决方案,一是用,另一个是用soft hyphen &shy;。说实话这两个东西本人都是第一次见到。google + 实验之后,发现不是所有浏览器都支持,&shy;则没有起到预期的效果,也就是说并没有把字符串从“/”前面断开。 继续google,发现后者没有效果
Opencv学习——图像融合
Opencv相关函数:C++: void seamlessClone(InputArray src, InputArray dst, InputArray mask, Point p, OutputArray blend, int flags)图像融合基本原理:泊松克隆,与图像的梯度和散度相关,具体的原理可查看 http://blog.csdn.net/hjimce/article/detail
ArcGIS10.0操作之七——多边形开洞
1、设置好snaping   2、选中要挖洞的多边形,用editor工具条的cut polygons tool,画出切割线要首尾相连   最后删除切割下的部分就行了,也就是把69删除就行了
FindContours的算法原理
FindContours Comments from the Wiki int cvFindContours(CvArr* image, CvMemStorage* storage, CvSeq** first_contour, intheader_size=sizeof(CvContour), int mode=CV_RETR_LIST, int method=CV_CHAI
QT开发(十四)——QT绘图系统
QT开发(十四)——QT绘图系统一、QT绘图原理    Qt4中的2D绘图系统称为Arthur绘图系统,可以使用相同的API在屏幕上和绘图设备上进行绘制,主要基于QPainter、QPainterDevice和 QPainterEngine。QPainter执行绘图操作,QPainterDevice提供绘图设备,是一个二维空间的抽象,QPainterEngine提供一些接口。QPainter用来执
AD16中敷铜与导线连接的方法
问题: AD16中敷铜与导线连接,在对敷铜进行Repour操作后,往往会把连接的导线与该敷铜区域分割开,而这并不是我们想要的效果; 如图所示: 解决办法: 选中敷铜区域,右键选择Properties…,在Net Options一栏中, 下拉选择框中,由Pour Over Same Net Polygons Only 改为Pour Over All Same Net Objects, ...
相关热词 c#中dns类 c#合并的excel c# implicit c#怎么保留3个小数点 c# 串口通信、 网络调试助手c# c# 泛型比较大小 c#解压分卷问题 c#启动居中 c# 逻辑或运算符
立即提问