Description During a voyage of the starship Hakodate-maru (see Problem 1406), researchers found strange synchronized movements of stars. Having heard these observations, Dr. Extreme proposed a theory of “super stars”. Do not take this term as a description of actors or singers. It is a revolutionar...

题目描述 给出N个点，让你画一个最小的包含所有点的圆。 输入格式 先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0) 输出格式 输出圆的半径，及圆心的坐标，保留10位小数 输入输出样例 输入 #1复制 6 8.0 9.0 4.0 7.5 1.0 2.0 5.1 8.7 9.0 2.0 4.5 1.0 输出 #1复制 5.0000000000 5.0000000000 5.0000000000 说明/提示 5.00 5.00 5.0 随机增量法： 我们先把所有点随机化（这点很重要）。 ...

题目描述 农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。 输入格式 输入数据的第一行包括一个整数 N。N（0 <= N <= 10,000）表示农夫约翰想要围住的放牧点的数目。接下来 N 行，每行由两个实数组成，Xi 和 Yi,对应平面上的放牧点坐标（-1,000,000 <= Xi,Yi <= 1,000,000）。数字用小数表示。 输出格式 输出必须包括一个实数，表示必须的围栏的长度。答案保留两位小数。 输入输出样例 输入 #1复制 4 ...

例题：POJ 2187 旋转卡壳一般用来求平面中最远的两点的距离。 我们很明显的可以发现，最远的两个点必然在凸包上，于是我们求出凸包之后，扫对踵点。利用凸包上的点依次与对应边产生的距离成单峰函数,面积上升到最高点后，又会下降。(具体证明可以从凸包定义入手 用反证法解决) 然后就可以O(n) 得到最远的距离了，但是求Graham求凸包是 O(n*logn) 的。 AC代码： #include<cmath> #include<cstdio> #include<cstdlib> #include<iostream> #includ...

dijkstra因为不能处理负权最短路，所以不能用来费用流的增广。 但是如果我们利用Johnson的思想，加一个势函数，把负变正，就能跑费用流了。 维护势函数也很简单，每次跑完dijkstra之后，对于最短路非INF的点，令势函数加上最短路即可。 dijkstra跑增广时直接把 w[i] -> w[i] + h[u] - h[v] ，对于u到v的边。 三种费用流比较： EK+spfa：简单好写，速度慢。 EK+势函数的dijkstra：对于边多的情况很快。 ZKW：稠密图+流量大+费用小的情况比较快。 代码： #pragma GCC optimize(2) #inc...

例题：hdu 1115 给出一堆点，求多边形的重心。 我们可以把多边形划分为许多三角形。三角形的重心很简单： x = ( x1 + x2 + x3 ) / 3 , y = ( y1 + y2 + y3 ) / 3 多边形的重心公式为： 借用大佬博客的图片：https://blog.csdn.net/u010499449/article/details/38168677 公式当中的行列式，其实就是三角形的面积，我们可以利用叉积来求。 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#defi...

Simpson是什么呢？ 就是如果我们要求一个积分，但是里面的f(x)十分麻烦，于是我们就需要用Simpson的抛物线来近似最后的答案。 加一个自适应就是适应精度，当精度很小的时候，就直接返回。 Simpson公式： 例题：Simpson例题 AC代码： #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int long long using namespace std; double a,b,c,d,L,R; inline double f(double x){return (c*x+d)/(a...

泰森多边形： 大概就是一个平面划分，平面上的每个点划分到离它最近的关键点上。 Delaunay三角剖分和泰森多边形是对偶图。 Delaunay三角剖分： 定理：对于任何一种三角剖分，三角形个数和外围凸包点数之和为2n-2。 Delaunay三角剖分的性质 1.平面上的点集有且仅有唯一的Delaunay三角剖分（除出现四点共圆的情况，这时泰森多边形有顶点属于四个区域）。 2.任意一个Delaunay三角形的外接圆不包含点集中的其他点。（称为Delaunay三角形的空圆性质）。 3.Delaunay三角剖分相比其他的三角剖分，所有三角形的最小角最大

题目描述 你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。 输入格式 第一行: 两个整数N(2&...

题目链接：CF311E Biologist 最小割（最大权闭合子图）。 对于每个点有两个状态，而不是以往最大权闭合子图的一个状态。所以我们要对于0,1的点判断一下。 如果点为0，那么S连向此点，表示此点变为1的代价。 如果点为1，那么此点连向T，表示此点变为0的代价。 那么对于我们的需求： 如果需要为1，那么连接T。 如果需要为0，那么连接S。 自己画画图就能知道了，因为这样能保证不改变的必须要代价。 对于每一个需求，如果未完成会付出代价，那么连接虚点的流量为 获得价值+代价 即可。 否则流量为 获得代价。 然后总和就是每个需求的值之和（不能加上代价），最后减去最小割即可。 ...

E. Tourism time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Alex decided to go on a touristic trip over the country. For simplicity let’s assume that the country has n cities and m bidirectional roads connecting them. Alex lives in city s an...

带花树主要用来找一般图的最大匹配。 例题：带花树例题 如果是二分图，我们可以很简单的用匈牙利或者网络流等等方法找出来最大匹配。 但是如果不是二分图呢？（有奇环） 我们就需要用到带花树了。 主要步骤： 首先，奇环中有2k+1个点，所以最多有k组匹配。这就是说，有一个点没有匹配，即这个点在环内两边的连边都不是匹配边，也只有这个点可以向环外连边。 所以我们就可把整个奇环缩成一个点。缩完点后的图如果可以找到一条增广路，那么原图中也可以找到一条增广路，因为如果增广路经过奇环那么奇环内的增广路可以还原出来。 搜索到了一个未标记的点，有两种情况。如果这个未标记点有匹配，那么把这个点设为B...

K Subsequence Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 3577 Accepted Submission(s): 898 Problem Description Master QWsin is dating with Sindar. And now they are in a restaurant, the restaurant has n dishes in order. For each dish, it has...

E. Beautiful Mirrors time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Creatnx has n mirrors, numbered from 1 to n. Every day, Creatnx asks exactly one mirror “Am I beautiful?”. The i-th mirror will tell Creatnx that he is beautiful with prob...