关键词：
首先我写了个凸包就溜了
这是最小圆覆盖问题，今晚学了一下
先随机化点，一个个加入
假设当前圆心为o，半径为r，加入的点为i
若i不在圆里面，令圆心为i，半径为0
再重新从1~i-1不停找j不在圆里面，令圆心为ij中点，直径为ij距离
再重新在1~j-1不停找k不在圆里面，三点可确定一圆，初中数学
复杂度看似O(n^3)实则O(n)，好玄学
坑点：注意如果用点斜式表示方程有斜率为不存在的情况，需要特判
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; const double eps=1e-8; double sqr(double x)return x*x; struct point double x,y;point() point(double X,double Y)x=X,y=Y; ; double getdis(point p1,point p2)return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y)); point middle(point p1,point p2)return point((p1.x+p2.x)/2,(p1.y+p2.y)/2); double slope (point p1,point p2) if(p2.x==p1.x)return 0; return (p2.y-p1.y)/(p2.x-p1.x); double multi(point p1,point p2,point p0) double x1,y1,x2,y2; x1=p1.x-p0.x; y1=p1.y-p0.y; x2=p2.x-p0.x; y2=p2.y-p0.y; return x1*y2-x2*y1; struct segment double k,b;segment() segment(double K,double B)k=K,b=B; ; segment getseg(double k,point pp)return segment(k,pp.y-k*pp.x); point intersection(segment s1,segment s2) double x=(s2.b-s1.b)/(s1.k-s2.k); double y=s1.k*x+s1.b; return point(x,y); //--------------------------------------simple-------------------------------------------------------- int n; point p[1100000]; bool cmp(point p1,point p2) double d=multi(p1,p2,p[1]); if(fabs(d)<=eps)return getdis(p1,p[1])<getdis(p2,p[1]); else return d>0; int top,sta[1100000]; void graham() sort(p+2,p+n+1,cmp); top=0;sta[++top]=1,sta[++top]=2; double g; for(int i=3;i<=n;i++) while(top>=2) g=multi(p[sta[top]],p[i],p[sta[top-1]]); if(g<0||fabs(g)<=eps)top--; else break; sta[++top]=i; //------------------------------------graham---------------------------------------------------------- point getcore(point p1,point p2,point p3) double g=multi(p1,p2,p3); if(fabs(g)<=eps) double d1=getdis(p1,p2),d2=getdis(p1,p3),d3=getdis(p2,p3); if(d1>d2&&d1>d3)return middle(p1,p2); if(d2>d1&&d2>d3)return middle(p1,p3); if(d3>d1&&d3>d2)return middle(p2,p3); else segment s1,s2; if(slope(p1,p2)==0) s1=getseg(-1/slope(p1,p3),middle(p1,p3)); s2=getseg(-1/slope(p2,p3),middle(p2,p3)); else if(slope(p1,p3)==0) s1=getseg(-1/slope(p1,p2),middle(p1,p2)); s2=getseg(-1/slope(p2,p3),middle(p2,p3)); else s1=getseg(-1/slope(p1,p2),middle(p1,p2)); s2=getseg(-1/slope(p1,p3),middle(p1,p3)); return intersection(s1,s2); void circlecover() random_shuffle(sta+1,sta+top+1); point o=p[sta[1]];double r=0,d; for(int i=2;i<=top;i++) if(getdis(o,p[sta[i]])>r) o=p[sta[i]],r=0; for(int j=1;j<i;j++) if(getdis(o,p[sta[j]])>r) o=middle(p[sta[i]],p[sta[j]]),r=getdis(o,p[sta[i]]); for(int k=1;k<j;k++) if(getdis(o,p[sta[k]])>r) o=getcore(p[sta[i]],p[sta[j]],p[sta[k]]),r=getdis(o,p[sta[i]]); printf("%.2lf %.2lf %.2lf ",o.x,o.y,r); //------------------------------------solve---------------------------------------------------------- int main() scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); if(p[i].y<p[1].y||(p[i].y==p[1].y&&p[i].x<p[1].x)) swap(p[i],p[1]); graham(); circlecover(); return 0;
[日常摸鱼]bzoj2823[ahoi2012]信号塔
题意：$n$个点，求最小圆覆盖，$nleq5e5$ 这题数据是随机的hhh我们可以先求出凸包然后对凸包上的点求最小圆覆盖…（不过直接求应该也行？）反正随便写好像都能过…#include<cstdio>#include<algorithm>#include<cstd... 查看详情
bzoj2823:[ahoi2012]信号塔&&1336:[balkan2002]alien最小圆覆盖&&1337:最小圆覆盖(代码片段)
首先我写了个凸包就溜了这是最小圆覆盖问题，今晚学了一下先随机化点，一个个加入假设当前圆心为o，半径为r，加入的点为i若i不在圆里面，令圆心为i，半径为0再重新从1~i-1不停找j不在圆里面，令圆心为ij中点，直径为ij距... 查看详情
[ahoi2012]信号塔(代码片段)
传送门最小圆覆盖的板子题，和bzoj1336一样，双倍经验题代码：#include<iostream>#include<algorithm>#include<cmath>usingnamespacestd;voidread(int&x)charch;boolok;for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;for(x=0;isdigit(ch);x=x*... 查看详情
p2533[ahoi2012]信号塔(代码片段)
传送门据说是一个叫做随机增量法的东西枚举(i)，如果不在圆中将它设为圆心枚举(j)，如果不在圆中将((i,j))成为新的圆的直径枚举(k)，如果不在圆中让(i,j,k)组成的三角形的外接圆成为新的圆据说在随机数据的情况下期望(O(n))，... 查看详情
bzoj1968:[ahoi2005]common约数研究
二次联通门:BZOJ1968:[Ahoi2005]COMMON约数研究 /*BZOJ1968:[Ahoi2005]COMMON约数研究SB题*/#include<cstdio>#definergregistertypedeflonglongLL;intmain(intargc,char*argv[]){intN;scanf("%d",&am 查看详情
bzoj2822:[ahoi2012]树屋阶梯
BZOJ2822:[AHOI2012]树屋阶梯Description暑假期间，小龙报名了一个模拟野外生存作战训练班来锻炼体魄，训练的第一个晚上，教官就给他们出了个难题。由于地上露营湿气重，必须选择在高处的树屋露营。小龙分配的树屋建立在一颗高... 查看详情
bzoj2822[ahoi2012]树屋阶梯(卡特兰数)
2822:[AHOI2012]树屋阶梯TimeLimit: 1Sec MemoryLimit: 128MBSubmit: 879 Solved: 513[Submit][Status][Discuss]Description暑假期间，小龙报名了一个模拟野外生存作战训练班来锻炼体魄，训练的第一个晚上，教官就给他们出了 查看详情
bzoj2822:[ahoi2012]树屋阶梯
Description求拼成阶梯状的方案数.Sol高精度+Catalan数.我们可以把最后一行无线延伸,所有就很容易看出Catalan数了.(f_n=f_0f_{n-1}+f_1f_{n-2}+f_2f_{n-3}+...+f_{n-1}f_0)这就是Catalan数了,高精贴板子...Code/************************************************* 查看详情
bzoj2822[ahoi2012]树屋阶梯卡特兰数+高精
这道题随便弄几个数就发现是卡特兰数然而为什么是呢？我们发现我们在增加一列时，如果这一个东西（那一列）他就一格，那么就是上一次的方案数，并没有任何改变，他占满了也是，然后他要是占两格呢，就是把原来的切成... 查看详情
bzoj3236:[ahoi2013]作业
3236:[Ahoi2013]作业TimeLimit:100Sec MemoryLimit:512MBSubmit:1393 Solved:562[Submit][Status][Discuss]Description InputOutputSampleInput341221213121113132323SampleOutput22113221 查看详情
bzoj1800:[ahoi2009]fly飞行棋
二次联通门: BZOJ1800:[Ahoi2009]fly飞行棋 /*BZOJ1800:[Ahoi2009]fly飞行棋乱搞一下就好*/#include<cstdio>#include<iostream>#definergregisterinlinevoidread(int&n){rgintc=getchar( 查看详情
[bzoj3238][ahoi2013]差异
3238:[Ahoi2013]差异TimeLimit:20Sec MemoryLimit:512MBSubmit:3394 Solved:1542[Submit][Status][Discuss]DescriptionInput一行，一个字符串SOutput 一行，一个整数，表示所求值SampleInputcacaoSampleOutput54 查看详情
bzoj1406:[ahoi2007]密码箱
二次联通门: BZOJ1406:[AHOI2007]密码箱 /*BZOJ1406:[AHOI2007]密码箱数论要求x^2≡1(modn)可以转换为x^2-k*n=1(x+1)*(x-1)=k*n设n=a*b则a*b|(x+1)*(x-1)那么枚举b即可*/#include<cstdio>#include<cmath> 查看详情
bzoj1968ahoi2005common约数研究
1968:[Ahoi2005]COMMON约数研究TimeLimit: 1Sec MemoryLimit: 64MBSubmit: 1492 Solved: 1139[Submit][Status][Discuss]DescriptionInput只有一行一个整数N（0<N<1000000）。Outpu 查看详情
bzoj32383238:[ahoi2013]差异（sam）
3238:[Ahoi2013]差异TimeLimit: 20Sec MemoryLimit: 512MBSubmit: 3047 Solved: 1375DescriptionInput一行，一个字符串SOutput 一行，一个整数，表示所求值SampleInputcacaoSampleOut 查看详情
bzoj1787[ahoi2008]meet紧急集合
1787:[Ahoi2008]Meet紧急集合TimeLimit: 20Sec MemoryLimit: 162MBSubmit: 2466 Solved: 1117[Submit][Status][Discuss]DescriptionInputOutputSampleInput64122324455645663 查看详情
bzoj1787:[ahoi2008]meet紧急集合
1787:[Ahoi2008]Meet紧急集合TimeLimit: 20Sec MemoryLimit: 162MBSubmit: 3016 Solved: 1344[Submit][Status][Discuss]DescriptionInputOutputSampleInput64122324455645663 查看详情
bzoj3236:[ahoi2013]作业（缺线段树）
3236:[Ahoi2013]作业TimeLimit: 100Sec MemoryLimit: 512MBSubmit: 1744 Solved: 702[Submit][Status][Discuss]Description InputOutputSampleInput34122121312111313 查看详情