这题一上来首先想到的是能否用数学方法来求得这个点..比如说画一个半径最小的圆使其与所有线段相交或相切…那么圆心就是所求..想法似乎没问题..但怎么来求是毫无头绪~想了良久也没想出用数学的方法如何实现…
还是用枚举了…题目范围不大..并且精度要求不高..将整个( 0 , 0 ) ~ ( 100 ,100 ) 的连续空间离散分成1000个每个相距0.1的点..枚举每个点..定能找到答案..复杂度是 N*O(100^2)…估计最大数据时间大概需要十秒..发现这个时间是可以有优化空间的…我就直接用二分了..每次枚举9个点 ( 正方形平均的9个点 )…找到最有点后再以这个点为九个点的中心点缩小步长再尝试9个点..直道枚举的两点间相差<0.01..也就是步长<0.01…
还有很重要的一个问题..枚举了一个点如何求出其到某线段的最短距离?..要分两种情况..第一种是这个点做垂线会落到这个线段上…这种情况用差乘求出这个点与线段构成的三角形面积*2…然后再除以这个线段的长度就是垂线的长度…而第二种情况是这个点对线段做出的垂线在线段外..那么最短的距离只可能是到线段两个端点距离的最短那个..如何判断这两种情况…其实出现第二种情况是因为这个点与线段构成的三角形是钝角三角形..并且不是这个点的两侧是钝角..是另外两个角有一个是钝角..如何判断钝角三角形..先求出三条边的长度..都知道坐标这个很好求…当x1^2+x2^2<x3^2…代表x1与x2的夹角是钝角…
Program:
分享到:
相关推荐
usaco section2.3--section5.5源程序。。。。。。。。。。。。。。。。
pku acm上的一系列usaco题目都可以在这里找到测试数据以及源代码,不过题目的名字和pku上有得有点出入,需要自己去比较一下,2002年
pku acm上的一系列usaco题目都可以在这里找到测试数据以及源代码,不过题目的名字和pku上有得有点出入,需要自己去比较一下,2001年
usaco测试数据+标程 usaco的section1到section5的所有测试数据 以及标准程序
USACO题目,Greedy Gift Givers
此c++代码实现了USACO上Bessie Come Home的问题,并运用了弗洛伊德算法
usaco5.2解题报告1
我的USACO题解和程序
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
USACO1-5单元AC的代码~ 1 Chapter1 1.1 Section 1.1 1.2 Section 1.2 1.3 Section 1.3 1.4 Section 1.4 1.5 Section 1.5 2 Chapter2 2.1 Section 2.1 2.2 Section 2.2 2.3 Section 2.3 2.4 Section 2.4 3 Chapter3 ...
CP问题 USACO,IOI,cp-algo,Code Jam和Hacker Cup档案中大多数问题的解决方案和一些解释。
这是USACO2001-2007月赛全集。 usaco是美国中学生的官方竞赛网站。是美国著名在线题库,专门为信息学竞赛选手准备。推荐直接阅读英语原文,既准确可靠又可提高英语水平。做题方式模拟正式比赛,采用标准测评机、文件...
usaco 2010-2011 nov news,喜欢usaco的朋友可以看看
usaco 合集,全部英文原题和中文译题,测试数据以及答案。还有讲解报告
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
USACO培训页面美国计算机奥林匹克训练页2015年6月17日开始
USACO题解及中文译题1.1.1-2.4.5 题目为TXT格式文档,代码为C++语言所编写
usaco 3到6章讲解
usaco 合集,包括英文原题和中文译题,测试数据以及答案,很全啊!usaco 合集usaco 合集usaco 合集usaco 合集
USACO题库绝大部份的官方测试数据