Current position : 首页 >> 凸包
PKU2019数据结构与算法实习期末考试
http://dapractise.openjudge.cn/2019finalexam2/排队[crayon-692bb70244fb3246044147/]树状数组过线段树不过[crayon-692bb70244fbf741350209/]线段树求最大数[crayon-692bb70244fc7335701288/]关键词搜索[crayon-692bb70244fd0511995575/]旅行最短路[crayon-692bb70244fe1668539764/]强连通分量[crayon-692bb70244fec578002785/]统计不同子串[crayon-692bb70244ffc844659783/]匹配网络流模板[crayon-692bb70245012941910000/]线性...
PKU2019数据结构与算法实习作业 22~30
题目来源：http://dapractise.openjudge.cn/2019hwall/POJ3436ACMComputerFactory[crayon-692bb70247469095424385/]POJ2112OptimalMilking[crayon-692bb70247482879117456/]POJ1274ThePerfectStall用邻接矩阵写的[crayon-692bb70247492296264410/]POJ1269IntersectingLines[crayon-692bb7024749e970527747/]POJ1569MyacmTriangles[crayon-692bb702474a5685399586/]POJ1039Pipe[crayon-692bb70247...
算法设计与分析讨论班上机作业
凸包A:WallPOJ1113求凸包周长加一个圆[crayon-692bb7024825e947929052/]B:ScrambledPolygonPOJ2007排序凸包上的点[crayon-692bb70248269778186788/]动态规划G题真的坑A:Fourier’sLinesPOJ1923[crayon-692bb7024826e472269152/]B:TourPOJ2677[crayon-692bb70248273848018027/]C:IncreasingSequencesPOJ1239[crayon-692bb70248278899879199/]D:Charlie’sChangePOJ1787[crayon-692bb7024827f828...
2017ACM萧山训练第5场(2016 Pacific Northwest – Division 1)
E.Enclosure做出大小两个凸包，即所有点的凸包和前k个点的凸包按动态凸包的思路，新加入的点会把小凸包上连续的一些点弹出，这些点是一个连续的区间相当于切掉凸包的一个角，加入一个三角形若在大凸包上顺时针枚举一个加入的点，这个区间左右端点也是顺时针转的，类似旋转卡壳切掉部分的面积顺便维护由于坐标范围较大，用double精度会炸[crayon-692bb702490dc021228909/]G.MaximumIslandsL的上下左右直接贪心为W然后剩下的就...
「topcoder」Single Round Match 652 – Round 1 Div2
topcoder怎么会把客户端做成这样差评第一场只能打div2TAT250Youaregivenastringsconsistingoflowercaseletters.Weassigntheletters'a'to'z'valuesof1to26,respectively.WewilldenotethevalueassignedtotheletterXbyval[X].Forexample,val['a']=1andval['e']=5.Wedefinethevalueofthestringsasfollows.Foreachletters[i],letk[i]bethenumberoflettersinsthatarelessthanorequaltos[i],includings[i]itself.Then,thevalu...
「BZOJ2829」信用卡凸包
.jpg)
DescriptionInputOutputSampleInput26.02.00.00.00.00.02.0-2.01.5707963268SampleOutput21.66HINT本样例中的2张信用卡的轮廓在上图中用实线标出，如果视1.5707963268为Pi/2(pi为圆周率),则其凸包的周长为16+4*sqrt(2)题解把圆形拿出来求凸包周长，最后加上一个圆的周长[crayon-692bb7024a73e358939212/] ...
「POJ2187」Beauty Contest
DescriptionBessie,FarmerJohn'sprizecow,hasjustwonfirstplaceinabovinebeautycontest,earningthetitle'MissCowWorld'.Asaresult,BessiewillmakeatourofN(2<=N<=50,000)farmsaroundtheworldinordertospreadgoodwillbetweenfarmersandtheircows.Forsimplicity,theworldwillberepresentedasatwo-dimensionalplane,whereeachfarmislocatedatapairofintegercoordinates(x,y),eachhavingavalueintherange-10,000...1...
「BZOJ1185」[HNOI2007] 最小矩形覆盖
![「BZOJ1185」[HNOI2007] 最小矩形覆盖](http://www.lydsy.com/JudgeOnline/images/1185_1.jpg)
Description题解首先有一个结论，矩形的一条边一定在凸包上！！！枚举凸包上的边用旋转卡壳在凸包上找矩形另外三点。。。注意精度问题[crayon-692bb7024bd82075369788/] ...
「BZOJ2300」[HAOI2011] 防线修建
![「BZOJ2300」[HAOI2011] 防线修建](http://hzwer.com/wp-content/themes/ly/image/image_post/2014-12-10_11-16-36.jpg)
Description近来A国和B国的矛盾激化，为了预防不测，A国准备修建一条长长的防线，当然修建防线的话，肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决，到底该把哪些城市作为保护对象呢？又由于A国的经费有限，所以希望你能帮忙完成如下的一个任务：给出你所有的A国城市坐标A国上层经过讨论，考虑到经济问题，决定取消对i城市的保护，也就是说i城市不需要在防线内了A国上层询问对于剩下要保护的城市，修...
「BZOJ1670」[Usaco2006 Oct] Building the Moat护城河的挖掘
![「BZOJ1670」[Usaco2006 Oct] Building the Moat护城河的挖掘](http://www.lydsy.com:808/JudgeOnline/upload/201409/111.jpg)
Description为了防止口渴的食蚁兽进入他的农场，FarmerJohn决定在他的农场周围挖一条护城河。农场里一共有N(8<=N<=5,000)股泉水，并且，护城河总是笔直地连接在河道上的相邻的两股泉水。护城河必须能保护所有的泉水，也就是说，能包围所有的泉水。泉水一定在护城河的内部，或者恰好在河道上。当然，护城河构成一个封闭的环。挖护城河是一项昂贵的工程，于是，节约的FJ希望护城河的总长度尽量小。请你写个程序计算一下...
「BZOJ1069」[SCOI2007] 最大土地面积
![「BZOJ1069」[SCOI2007] 最大土地面积](http://hzwer.com/wp-content/themes/ly/image/image_post/2014-12-10_11-17-37.jpg)
Description在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成的多边形面积最大。Input第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。Output最大的多边形面积，答案精确到小数点后3位。SampleInput5001011010.50.5SampleOutput1.000HINT数据范围n<=2000,|x|,|y|<=100000题解n=2000。。。所以可以枚举一条对角线然后在两边分别找一个...
「cogs896」圈奶牛
描述农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。PROGRAMNAME:fcINPUTFORMAT(filefc.in)输入数据的第一行包括一个整数 N。N（0<=N<=10,000）表示农夫约翰想要围住的放牧点的数目。接下来N 行，每行由两个实数组成，Xi 和 Yi,对应平面上的放牧点坐标（-1...
近期评论