洛谷暂无评定题目新鲜出炉，本题解非洛谷题解
让我们看一看题
题目描述
We call any sequence of points in the plane a plot.
We intend to replace a given plot (P_1,\cdots,P_n)(P1,⋯,Pn) with another that will have at most mm points (m\le nm≤n) in such a way that it "resembles" the original plot best.
The new plot is created as follows. The sequence of points P_1,\cdots,P_nP1,⋯,Pn can be partitioned into ss (s\le ms≤m) contiguous subsequences:
(P_{k_0+1},\cdots,P_{k_1}),(P_{k_1+1},\cdots,P_{k_2}),\cdots,(P_{k_{s-1}+1},\cdots,P_{k_s})(Pk0+1,⋯,Pk1),(Pk1+1,⋯,Pk2),⋯,(Pks−1+1,⋯,Pks) where 0=k_0<k_1<k_2<\cdots<k_s=n0=k0<k1<k2<⋯<ks=n,and afterwards each subsequence (P_{k_{i-1}+1},\cdots,P_{k_i})(Pki−1+1,⋯,Pki), for i=1,\cdots,si=1,⋯,s,is replaced by a new point Q_iQi.
In that case we say that each of the points P_{k_{i-1}+1},\cdots,P_{k_i}Pki−1+1,⋯,Pki has been contracted to the point Q_iQi.
As a result a new plot, represented by the points Q_1,\cdots,Q_sQ1,⋯,Qs, is created.
The measure of such plot's resemblance to the original is the maximum distance of all the points P_1,\cdots,P_nP1,⋯,Pn to the point it has been contracted to:
max_{i=1,\cdots,s}(max_{j=k_{i-1}+1,\cdots,k_i}(d(P_j,Q_i)))maxi=1,⋯,s(maxj=ki−1+1,⋯,ki(d(Pj,Qi))) where d(P_j,Q_i)d(Pj,Qi) denotes the distance between P_jPj and Q_iQi, given by the well-known formula:
d((x_1,y_1),(x_2,y_2))=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}d((x1,y1),(x2,y2))=(x2−x1)2+(y2−y1)2
An exemplary plot P_1,\cdots,P_7P1,⋯,P7 and the new plot (Q_1,Q_2)(Q1,Q2), where (P_1,\cdots,P_4)(P1,⋯,P4) are contracted to Q_1Q1, whereas (P_5,P_6,P_7)(P5,P6,P7) to Q_2Q2.
For a given plot consisting of nn points, you are to find the plot that resembles it most while having at most mm points, where the partitioning into contiguous subsequences is arbitrary.
Due to limited precision of floating point operations, a result is deemed correct if its resemblance to the given plot is larger than the optimum resemblance by at most 0.0000010.000001.
给定n个点，要求把n个点分成不多于m段，使得求出每段的最小覆盖圆的半径后，最大的半径最小。
输入格式
In the first line of the standard input there are two integers nn and mm, 1\le m\le n\le 100\ 0001≤m≤n≤100 000, separated by a single space.
Each of the following nn lines holds two integers, separated by a single space.
输出格式
In the first line of the standard output one real number dd should be printed out, the resemblance measure of the plot found to the original one.
In the second line of the standard output there should be another integer ss, 1\le s\le m1≤s≤m.
Next, the following ss lines should specify the coordinates of the points Q_1,\cdots,Q_sQ1,⋯,Qs,one point per line.
Thus the (i+2)(i+2)-th line should give two real numbers u_iui and v_ivi, separated by a single space, that denote the coordinates (u_i,v_i)(ui,vi) of the point Q_iQi.All the real numbers should be printed with at most 15 digits after the decimal point.
输入输出样例
输入 #1
7 2 2 0 0 4 4 4 4 2 8 2 11 3 14 2
输出 #1
3.00000000 2 2.00000000 1.76393202 11.00000000 1.99998199
说明/提示
给定n个点，要求把n个点分成不多于m段，使得求出每段的最小覆盖圆的半径后，最大的半径最小。
文字呈现较乱，下面图片呈现：
好，题目看完了，其实这个题目是想让我们求最小覆盖圆的最大半径最小，这其实很简（keng）单(die)。我只用了一会（三）儿（天）就做完了
代码也很好理解（坑爹），我自（靠）己（大）绞（佬）劲（的）脑（帮）汁（助）才想出来
好吧，废话不多说上链接，上代码！！！
https://www.luogu.com.cn/problem/P3517
https://www.luogu.com.cn/problem/P3517通关代码：
#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define ll long long
#define hh puts("")
#define pc putchar
using namespace std;
const int N=100005;
int n,m,res[N][2],cnt,ci;
double eps=1e-10,R;
struct point {
double x,y;
} a[N],b[N],O;
inline int read() {
int ret=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {
if(ch=='-') ff=-ff;
ch=getchar();
}
while(isdigit(ch)) {
ret=(ret<<3)+(ret<<1)+ch-'0';
ch=getchar();
}
return ret*ff;
}
void write(int x) {
if(x<0) {
x=-x;
putchar('-');
}
if(x>9) write(x/10);
putchar(x%10+48);
}
void writeln(int x) {
write(x),hh;
}
point Mid(point A,point B) {
return (point) {
(A.x+B.x)/2,(A.y+B.y)/2
};
}
double dist(point A,point B) {
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
void getO(point A,point B,point C) {
double aa,bb,cc,dd,ee,ff;
aa=A.x-C.x;
bb=A.y-C.y;
cc=B.x-C.x;
dd=B.y-C.y;
ee=A.x*A.x+A.y*A.y-C.x*C.x-C.y*C.y;
ff=B.x*B.x+B.y*B.y-C.x*C.x-C.y*C.y;
O.x=(dd*ee-bb*ff)/(2*aa*dd-2*bb*cc);
O.y=(aa*ff-cc*ee)/(2*aa*dd-2*bb*cc);
R=dist(O,A);
}
void work(int l,int r) {
int tot=0;
for(int i=l; i<=r; i++) b[++tot]=a[i];
for(int i=1; i<=tot; i++) swap(b[i],b[rand()%tot+1]);
O=b[1],R=0;
for(int i=1; i<=tot; i++) {
if(dist(b[i],O)>R+eps) {
O=b[i],R=0;
for(int j=1; j<i; j++) {
if(dist(b[j],O)>R+eps) {
O=Mid(b[i],b[j]);
R=dist(O,b[i]);
for(int k=1; k<j; k++)
if(dist(b[k],O)>R+eps)
getO(b[i],b[j],b[k]);
}
}
}
}
}
bool check(double lim) {
cnt=0;
int ans;
for(int i=1; i<=n; i=ans+1) {
int k;
for(k=1; i+(1<<k)-1<=n; k++) {
work(i,i+(1<<k)-1);
if(R>lim+eps) break;
}
ans=i;
int l=i+(1<<(k-1))-1,r=min(n,i+(1<<k)-1);
while(l<=r) {
int mid=(l+r)>>1;
work(i,mid);
if(R<lim+eps) l=mid+1,ans=mid;
else r=mid-1;
}
cnt++;
res[cnt][0]=i,res[cnt][1]=ans;
if(cnt>m) return 0;
}
return 1;
}
signed main() {
srand(20031128);
n=read(),m=read();
for(int i=1; i<=n; i++) {
a[i].x=read();
a[i].y=read();
}
work(1,n);
double l=0,r=R;
if(m>1) {
ci=50;
while(ci--&&r-l>eps) {
double mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
}
check(r);
printf("%.8lf\n",r);
writeln(cnt);
for(int i=1; i<=cnt; i++) {
work(res[i][0],res[i][1]);
printf("%.8lf %.8lf\n",O.x,O.y);
}
return 0;
}代码属实有点长
思路：二分
嘻嘻嘻