2 casstina Casstina 于 2016.02.13 22:04 提问

入门小白求解北京2004ACM的Square题

入门小白开始啃题,然而啃不动(无奈摊手)
求大神帮忙解答(最好是有解释啦)(ฅ>ω<*ฅ)
SquareTime Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KBTotal submit users: 177, Accepted users: 26Problem 10002 : No special judgementProblem descriptionGiven a square at [0, 1] * [0, 1] that has N points ( P1, P2, ..., PN ) in the square (you may assume that different points can be at the same position), we can connect the N points and the four corners of the square with some line segments so that through these segments any two of the N+4 points can reach each other (directly or indirectly). The graph length is defined as the total length of the line segments. When N points' positions are fixed, there must exist a way of connecting them, such that it will make the shortest graph length. We can use LEN (P1, P2, ..., PN) to record the graph length using this way of connecting. 

In this situation, LEN (P1, P2, ..., PN) is a function of P1, P2, ..., PN. When P1, P2, ..., PN change their positions, LEN (P1, P2, ..., PN) also changes. It's easy to prove that there exist some P1', P2', ..., PN' in the square such that LEN (P1', P2', ..., PN') is at its minimum. 

Given the initial positions of N points, your task is to find out N points P1", P2", ..., PN" in the square such that |P1P1"| + |P2P2"| + ... + |PNPN"| is minimum and LEN (P1", P2", ..., PN") = LEN (P1', P2', ..., PN') . You are requested to output the value of |P1P1"| + |P2P2"| + ... + |PNPN"|, where |PiPi"| is the distance between Pi and Pi". 
?
For example, Figure-1 gives the initial position of P1 and the way of connecting to obtain LEN (P1). In Figure-2, it gives the position of P1", which is at the center of the square, and the way of connecting to obtain LEN (P1"). It can be proved that LEN (P1") = LEN (P1?); your job is to output the distance between P1 and P1".

InputThe input consists of several test cases. For each test case, the first line consists of one integer N (1 <= N <= 100), the number of points, and N lines follow to give the coordinates for every point in the following format: 
x y 

Here, x and y are float numbers within the value [0, 1]. 

A test case of N = 0 indicates the end of input, and should not be processed. 

OutputFor each test case, output the value of |P1P1"| + |P2P2"| + ... + |PNPN"|. The value should be rounded to three digits after the decimal point.

Sample Input1 0.2 0.5 2 0 0.5 0.5 0.5 0Sample Output0.300 0.500Judge Tips费马点

Problem SourceBeijing 2004图片

1个回答

caozhy
caozhy   Ds   Rxr 2016.02.13 22:09
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Sql小白入门(一)概述
虽然接触Sql的时间挺长了,但是一直都没有对Sql整理、总结,许多东西都是一知半解,所以将笔者学习Sql的笔记,整理为博客,对自己也算是一个归纳总结的过程,如果有错误之处,欢迎指出!开始博文!本系列博文内容摘录自《Sql入门经典》,在此向该书的作者表示感谢!     第一篇就先介绍一些概念! 一、首先来看几个定义。 1.什么是Sql? 结构化查询语言(Sql)是与关系型数据库进行通信的
小白如何快速入门数学建模
本人大三计算机专业,17年电工杯二等奖、MathorCup一等奖、国赛省一等奖、数创杯一等奖,奖项很水,但有必要介绍一下我参加建模的过程,希望对学弟学妹们有所帮助。 本人大一没想过比赛,大二为了我女朋友才跟她组队开始学着参加数学建模,从2017年2月开始上《数学建模》与《数学建模软件》两门选修课,从中对MATLAB有所了解,数学建模课程比较枯燥,仅仅是听过而已。 到2017年4月校赛,开始拿到
ACM小白入门
我放弃了使用了六年的pascal,放弃了学了一学期的java,自学了C++。个人认为使用c++参加acm是最好的选择。原因如下: (1)c++代码比pascal和java更加简洁 (2)效率比java要高 (3)学好c++,c的代码你也能看的懂 (4)大部分选手使用的是c++,不会的题目看题解你能看的懂我用的IDE是codeblocks,简单易用,安装起来也很方便。现在主要是在HDO
前端小白的学习历程
本文会不断更新,用于记录自己从0开始学前端的过程。 基础学习总结 下一步计划,疑问求助
从小白到入门(java web篇)
关于java web的入门~
小白如何快速入门软件测试
先说点我的测试经历,让大家都软件测试有些认识. 毕业后,拿着简历想都没想一头就扎到了苏州,作为一个北方女汉子,一直被“青石板小路回眸一笑的女子”的曼妙所感动,全无他因,事后说起,一朋友评价说我是个完全无脑的女子-:) 话说到了苏州,不但想象中的美景美有看到,经过了2/3个月的找工作之路,带着一个“无能”、“无知”、“我啥也不会”的极其低落的心情来到了北京,来北京只是想碰运气,因为人都说帝都工作
web前端小白入门教程
一小时学会写页面 作为一个懒癌晚期患者,总是习惯找各种简单的解决问题的方法,也习惯性把问题简单化,所以今天想分享给大家简单的web前端入门方法。 既然题目已经定了一个小时那么废话就不多说了,计时开始 1.什么是前端 简单来说,前端就是做网页(大神勿喷,本文一切从简) 2.前端技术 html,是首字母缩写,具体意义请百度,大家要记住“t”代表text,ok你们没有想错,text就是文本文
小白如何入门区块链技术
前几天我们已经学了如何学习的“道”和“术”,学完之后就应该落地到实践上,通过不断地实践练习,才能将这些 知识资源 转化为我们的 知识资本。如果你看完前面的文章后,觉得讲得真好,然后缺乏思考缺乏行动,然后就没有然后了。为了更好地指导你们如何实践,本篇文章我将与你分享我是如何将知识资源转化为我的知识资本的。 如果你开始对以太坊上去中心化应用的开发产生兴趣,希望马上可以动手实践,可以访问汇智网提...
web前端小白入门
 第一步:html+css学习 W3c、慕课网 第二步:Javascript学习 学习前端就好比如盖房子~ html就充当了房子结构这部分,也是房子的基础。 css呢,就好比咱们房子的装修,墙面什么颜色,什么风格,什么地板...这些给房子改变风格,样式的就是css javascript呢,就好比这个房子的功能,房子需要制冷吧,需要暖气吧,也需要上下水吧。这些功能性的就相当
零基础小白应该怎么入门编程开发
最近,在交流群里经常有苦逼小白问怎样学编程,对编程有兴趣但无从下手,这是个庞大到让大神们“无言以对”的命题。在知乎、CSDN等论坛上,许多同行也对此类问题进行了探讨,小编就其中认可度较高的回答进行了整理,以望给纠结的菜鸟们一些帮助,也欢迎大神们补充和拍砖。 1、决定学,要有兴趣并且是真正的下定决心 兴趣和耐心是老生常谈的话题,小编不在此唠叨,只要记住一点,现在程序员工资差异很大