关键词：
题目描述
给出一系列点p_1, p_2, ... , p_n，将其分成不多余m个连续的段，第i段内求一个点q_i，使得q_i到这段内点的距离的最大值的最大值最小
输入
第一行，n m
下面n行，每行两个整数，表示p_i的x y坐标
1<=m<=n<=100000
坐标范围[-1000000,1000000] 0<p,q,r<=150，输入中至少包含一个’N’
输出
第一行，q_i到这段内点的距离的最大值的最大值的最小值
第二行，分成的段数k
下面k行，每行两个实数，表示q_k的x y坐标
All the real numbers should be printed with at most 15 digits after the decimal point.
样例输入
7 2
2 0
0 4
4 4
4 2
8 2
11 3
14 2
样例输出
3.00000000
2
2.00000000 1.76393202
11.00000000 1.99998199
题解
二分+倍增+二分+最小圆覆盖
最大值最小，一眼二分答案。
考虑怎么判定：取前任意个点跑最小圆覆盖，直到半径大于mid为止，最后看分成段的数目是否超过m即可。
然而这样暴力跑是不行的，需要优化这个过程；同时直接再二分也是不可取的，因为二分的区间长度是满的，最坏情况下每段长度都为1，每段都需要$O(n\log n)$的时间来找，GG。
所以需要让求最小圆覆盖的点数只与每段长有关。考虑倍增，处理出第一个$j$，满足$2^j$个不满足条件。然后在$2^{j-1}$到$2^j$之间二分处理即可。这样第一部分时间复杂度为$O(len)$，第二部分时间复杂度为$O(len\log len)$，与n无关，所以可以满足时间要求。
因此总的时间复杂度为$O(n\log^2n)$，然而常数巨大。。。所以才给300s。。。
最小圆覆盖的求法参见 http://www.cnblogs.com/GXZlegend/p/7467029.html
CQzhangyu说卡精度，然而没看出来= = 1A了
#include <cstdio>
#include <algorithm>
#define N 100010
#define eps 1e-15
using namespace std;
int n , m , id[N] , tot;
double mid , x[N] , y[N] , ansx[N] , ansy[N];
inline double squ(double x)
{
return x * x;
}
bool check(int lp , int rp , double &vx , double &vy)
{
int i , j , k , len = rp - lp + 1;
double px = 0 , py = 0 , r = 0 , x1 , x2 , x3 , y1 , y2 , y3;
for(i = lp ; i <= rp ; i ++ ) id[i - lp + 1] = i;
random_shuffle(id + 1 , id + len + 1);
for(i = 1 ; i <= len ; i ++ )
{
if(squ(px - x[id[i]]) + squ(py - y[id[i]]) > r + eps)
{
px = x[id[i]] , py = y[id[i]] , r = 0;
for(j = 1 ; j < i ; j ++ )
{
if(squ(px - x[id[j]]) + squ(py - y[id[j]]) > r + eps)
{
px = (x[id[i]] + x[id[j]]) / 2 , py = (y[id[i]] + y[id[j]]) / 2 , r = (squ(x[id[i]] - x[id[j]]) + squ(y[id[i]] - y[id[j]])) / 4;
if(r > mid * mid + eps) return 0;
for(k = 1 ; k < j ; k ++ )
{
if(squ(px - x[id[k]]) + squ(py - y[id[k]]) > r + eps)
{
x1 = x[id[i]] , x2 = x[id[j]] , x3 = x[id[k]];
y1 = y[id[i]] , y2 = y[id[j]] , y3 = y[id[k]];
px = (x1 * x1 * (y2 - y3) + x2 * x2 * (y3 - y1) + x3 * x3 * (y1 - y2) - (y1 - y2) * (y2 - y3) * (y3 - y1)) / (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2;
py = ((x1 - x2) * (x2 - x3) * (x3 - x1) - y1 * y1 * (x2 - x3) - y2 * y2 * (x3 - x1) - y3 * y3 * (x1 - x2)) / (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2;
r = squ(px - x1) + squ(py - y1);
if(r > mid * mid + eps) return 0;
}
}
}
}
}
}
vx = px , vy = py;
return 1;
}
bool judge()
{
int i , len , last , l , r , mid;
bool flag;
double tmpx , tmpy;
tot = 0;
for(i = 1 ; i <= n ; i = last + 1)
{
if(tot == m) return 0;
flag = 0;
for(len = 1 ; !flag ; len <<= 1)
{
if(!check(i , min(i + len - 1 , n) , tmpx , tmpy))
{
flag = 1;
break;
}
else if(i + len - 1 >= n)
{
tot ++ , ansx[tot] = tmpx , ansy[tot] = tmpy;
return 1;
}
l = i + len;
}
r = min(i + len - 1 , n) , last = l - 1;
while(l <= r)
{
mid = (l + r) >> 1;
if(check(i , mid , tmpx , tmpy)) last = mid , l = mid + 1;
else r = mid - 1;
}
check(i , last , tmpx , tmpy) , tot ++ , ansx[tot] = tmpx , ansy[tot] = tmpy;
}
return 1;
}
int main()
{
srand(20011011);
int i , cnt = 50;
double l = 0 , r = 2e6;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++ ) scanf("%lf%lf" , &x[i] , &y[i]);
while(cnt -- )
{
mid = (l + r) / 2;
if(judge()) r = mid;
else l = mid;
}
printf("%.15lf\n" , r);
mid = r , judge();
printf("%d\n" , tot);
for(i = 1 ; i <= tot ; i ++ ) printf("%.15lf %.15lf\n" , ansx[i] , ansy[i]);
return 0;
}
bzoj2527[poi2011]meteors
...：http://www.lydsy.com/JudgeOnline/problem.php?id=2527【题解】整体二分思想，其实就是把一坨二分拿一起处理了。。。（事实上这题暴力好像。。不需要二分？）我们定义solve(l,r,al,ar)为当前二分区间为[l,r]，在这个区间的公司为id[al..ar]那... 查看详情
bzoj2527[poi2011]meteors：整体二分
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2527题意： 有n个国家和m个空间站，每个空间站都属于一个国家，一个国家可以有多个空间站，所有空间站按照顺序形成一个环，也就是说，m号空间站和1号空间站相邻。 现... 查看详情
bzoj2525[poi2011]dynamite二分+树形dp
【BZOJ2525】[Poi2011]DynamiteDescriptionByteotianCave的结构是一棵N个节点的树，其中某些点上面已经安置了炸.药，现在需要点燃M个点上的引线引爆所有的炸.药。某个点上的引线被点燃后的1单位时间内，在树上和它相邻的点的引线会被点... 查看详情
bzoj2527[poi2011]meteors整体二分+树状数组
题目描述有N个成员国。现在它发现了一颗新的星球，这颗星球的轨道被分为M份（第M份和第1份相邻），第i份上有第Ai个国家的太空站。这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。BIU的第i个成员国希望能够... 查看详情
bzoj2525:[poi2011]dynamite二分+树上贪心(代码片段)
一眼二分。然后重点是树上贪心部分长得像dp一样，设mn为子树内已炸点的最浅点，mx为子树内没有炸并且需要炸的最深点，然后转移直接从子树继承即可然后是判断当前u点是否需要炸，当mx[u]+mn[u]<=mid，当前子树可以自己消化... 查看详情
bzoj_2946_[poi2000]公共串_后缀数组+二分答案
BZOJ_2946_[Poi2000]公共串_后缀数组+二分答案Description 给出几个由小写字母构成的单词，求它们最长的公共子串的长度。任务：l 读入单词l 查看详情
[bzoj2946][poi2000]公共串_后缀数组_二分
...，中间加上$n-1$个不同的非字符集数组隔开。紧接着我们二分答案。然后扫$ht$数组，看一下是否存在连续的大于$mid$的一段满足包含了所有串。$ht$除了有一个值之外还存了一下 查看详情
[poi2011]plot
https://szkopul.edu.pl/problemset/problem/mzrTn1kzVBOAwVYn55LUeAai/site/?key=statement既卡常又卡精度...真的A不动...下次有机会重写吧 查看详情
bzoj4724[poi2017]podzielno数学+二分
【BZOJ4724】[POI2017]PodzielnoDescriptionB进制数，每个数字i(i=0,1,...,B-1)有a[i]个。你要用这些数字组成一个最大的B进制数X(不能有前导零，不需要用完所有数字)，使得X是B-1的倍数。q次询问，每次询问X在B进制下的第k位数字是什么(最低... 查看详情
bzoj2067[poi2004]szn二分+树上贪心
【BZOJ2067】[Poi2004]SZNDescriptionString-Toysjoint-stock公司需要你帮他们解决一个问题.他们想制造一个没有环的连通图模型.每个图都是由一些顶点和特定数量的边构成.每个顶点都可以连向许多的其他顶点.一个图是连通且无环的.图是由... 查看详情
bzoj2440:[中山市选2011]完全平方数二分答案+容斥原理+莫比乌斯反演
....com/JudgeOnline/problem.php?id=2440第一道莫比乌斯反演的题目。二分答案+容斥那里还是挺好想的。二分一个答案val，需要[1,val]之间存在的合法数字个数>=k即可。怎么判断呢？可以容斥，开始的时候有ans=val个，但是这里明显有些数字... 查看详情
bzoj2067[poi2004]szn——二分(代码片段)
...自己合并向上，所以ans=1+∑(1<=i<=n)(deg[i]-1)/2问题2：二分最长线段的长度，设f[x]表示自己带着的链的长度(即儿子中剩下的那一个带来的长度)，判断是否满足条件即可；如果当前节点有偶数个 查看详情
bzoj3872[poi2014]antcolony树形dp+二分
【BZOJ3872】[Poi2014]AntcolonyDescription给定一棵有n个节点的树。在每个叶子节点，有g群蚂蚁要从外面进来，其中第i群有m[i]只蚂蚁。这些蚂蚁会相继进入树中，而且要保证每一时刻每个节点最多只有一群蚂蚁。这些蚂蚁会按以下方式... 查看详情
[bzoj2527][poi2011]meteors
2527:[Poi2011]MeteorsTimeLimit:60Sec MemoryLimit:128MBSubmit:1807 Solved:646[Submit][Status][Discuss]DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinan 查看详情
bzoj2095[poi2010]bridges判断欧拉维护，最大流+二分(代码片段)
[Poi2010]BridgesTimeLimit: 10Sec MemoryLimit: 259MBSubmit: 1448 Solved: 510[Submit][Status][Discuss]DescriptionYYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连 查看详情
bzoj3524[poi2014]couriers（二分+蒙特卡罗）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3524 【题目大意】 给一个长度为n的序列a。1≤a[i]≤n。 m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。 如果存在，... 查看详情
bzoj2213[poi2011]differencedp
【BZOJ2213】[Poi2011]DifferenceDescriptionAwordconsistingoflower-caselettersoftheEnglishalphabet(‘a‘-‘z‘)isgiven.Wewouldliketochooseanon-emptycontiguous(i.e.one-piece)fragmentofthewordsoastomaximisethed 查看详情
做题poi2011r1-plot——最小圆覆盖&倍增(代码片段)
...出这个最小化的最大值和方案（圆心）。(n,mleq10^5)显然要二分答案。然后，一个区间就是越长越好。首先，考虑最小圆覆盖(O(n))的随机增量法，但为了保证复杂度，我们需要能够random_shuffle。如果直接按照编号顺序添加点，时间... 查看详情