bzoj1336/1337/2823[balkan2002]alien最小圆覆盖随机增量法

关键词：

题目描述

给出N个点，让你画一个最小的包含所有点的圆。

输入

先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)

输出

输出圆的半径，及圆心的坐标

样例输入

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

样例输出

5.00
5.00 5.00

题解

随机增量法求最小圆覆盖裸题

求法：设初始圆为某空圆，先枚举第一个点，如果不在当前圆内，则令当前圆为这一个点的最小圆覆盖并枚举第二个点，如果不在则变为这两个点的最小圆覆盖并枚举第三个点，如果不在则变为这三个点的最小圆覆盖。

看上去是三重循环，但是实际上时间复杂度为期望$O(n)$的，证明参见 http://blog.csdn.net/lthyxy/article/details/6661250。

需要先将点随机排序以防止被刻意卡掉。

另外求三个点的公共圆时可以直接套用坐标公式，参见代码。

#include <cmath>
#include <cstdio>
#include <algorithm>
#define N 100010
using namespace std;
const double eps = 1e-15;
double x[N] , y[N];
int id[N];
inline double squ(double x)
{
	return x * x;
}
int main()
{
	srand(20011011);
	int n , i , j , k;
	double px = 0 , py = 0 , r = 0 , x1 , x2 , x3 , y1 , y2 , y3;
	scanf("%d" , &n);
	for(i = 1 ; i <= n ; i ++ ) scanf("%lf%lf" , &x[i] , &y[i]) , id[i] = i;
	random_shuffle(id + 1 , id + n + 1);
	for(i = 1 ; i <= n ; 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;
					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);
						}
					}
				}
			}
		}
	}
	printf("%.15lf
%.15lf %.15lf
" , sqrt(r) , px , py);
	return 0;
}

bzoj1176:[balkan2007]mokia

1176:[Balkan2007]MokiaTimeLimit: 30Sec  MemoryLimit: 162MBSubmit: 2841  Solved: 1279[Submit][Status][Discuss]Description维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵 查看详情

[bzoj1176][balkan2007]mokia

1176:[Balkan2007]MokiaTimeLimit:30Sec  MemoryLimit:162MBSubmit:2633  Solved:1184[Submit][Status][Discuss]Description维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询 查看详情

bzoj千题计划144：bzoj1176:[balkan2007]mokia

http://www.lydsy.com/JudgeOnline/problem.php?id=1176 CDQ分治 #include<cstdio>#include<iostream>#include<algorithm>#definelowbit(x)x&-xusingnamespacestd;#defineN160001#def 查看详情

[bzoj1176][balkan2007]mokiacdq+树状数组(代码片段)

1176:[Balkan2007]MokiaTimeLimit: 30Sec  MemoryLimit: 162MBSubmit: 3134  Solved: 1395[Submit][Status][Discuss]Description维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵 查看详情

bzoj1174:[balkan2007]toponyms

TimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 735  Solved: 102[Submit][Status][Discuss]Description给你一个字符集合,你从其中找出一些字符串出来.希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化.Input第... 查看详情

bzoj1176[balkan2007]mokia

TimeLimit: 30Sec  MemoryLimit: 162MBSubmit: 2000  Solved: 890Description维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000 查看详情

bzoj1336[balkan2002]alien最小圆覆盖随机增量法

【BZOJ1336】[Balkan2002]Alien最小圆覆盖Description给出N个点，让你画一个最小的包含所有点的圆。Input先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)Output输出圆的半径，及圆心的坐标SampleInput68.09.04.07.51.02.05.... 查看详情

bzoj1174[balkan2007]toponymstrie树

题目描述给你一个字符集合,你从其中找出一些字符串出来.希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化.输入第一行给出数字N.N在[2,1000000]下面N行描述这些字符串,长度不超过20000。保证输入文件不超过10MB输... 查看详情

bzoj1176[balkan2007]mokia/bzoj2683简单题

bzoj1176题目描述维护一个W*W的矩阵，初始值均为S（题目描述有误，这里的S没有任何作用！）.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.输入第一行两个整数,S,W;其中... 查看详情

bzoj1173:[balkan2007]point

Description给出N个三维空间上的点.问有多少条直线,这些直线上至少有三个点.Input第一行给出数字N,N在[4,1000]下面N行,每行三个数字,用于描述点的坐标,其值在[-10000,10000]Output有多少条直线枚举直线的方向，对每个方向建一个图，若... 查看详情

bzoj1176：[balkan2007]mokia——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=1176Description（题面本人自行修改了一下）维护一个W*W的矩阵，初始值均为0.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.Input第一行... 查看详情

bzoj1176:[balkan2007]mokia

一道CDQ分治的模板题，然而我De了一上午Bug......按时间分成左右两半，按x坐标排序然后把y坐标丢到树状数组里，扫一遍遇到左边的就add,遇到右边的query几个弱智出了bug的点，一是先分了左右两半再排序，保证的是这次的左右是... 查看详情

bzoj3022[balkan2012]thebestteams（扫描线+线段树）

 【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3022 【题目大意】　　给定n个球员，第i个球员年龄为AGEi，水平为SKILLi。　　没有任何两个球员的水平相同。将这些球员按水平排序，　　对于一次比赛，你需要选... 查看详情

cdq分治入门--bzoj1176:[balkan2007]mokia

对w*w，w<=2000000的矩形，一开始全是0（或一开始全是s），n<=170000个操作，每次操作：矩阵内某点加上一个数，查某一个子矩阵的和，保证修改数<=160000，询问数<=10000。这还是一个比较明显的三维偏序：时间维，以及x和y... 查看详情

bzoj1176[balkan2007]mokia-cdq分治-树状数组

Description维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.Input第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小接下来每行为一下三种... 查看详情

bzoj2823:[ahoi2012]信号塔&&1336:[balkan2002]alien最小圆覆盖&&1337:最小圆覆盖(代码片段)

首先我写了个凸包就溜了这是最小圆覆盖问题，今晚学了一下先随机化点，一个个加入假设当前圆心为o，半径为r，加入的点为i若i不在圆里面，令圆心为i，半径为0再重新从1~i-1不停找j不在圆里面，令圆心为ij中点，直径为ij距... 查看详情

bzoj-1176&2683mokia&简单题cdq分治

1176:[Balkan2007]MokiaTimeLimit: 30Sec  MemoryLimit: 162MBSubmit: 1854  Solved: 821[Submit][Status][Discuss]Description维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的 查看详情

含有z和k的单词~~~~~多举几个~~~~我要英语名谢谢！！！

...g,alkylbenzenesulfonate,alkylbenzenesulfonates,alkylize.ashkenazi.bakelize,balkanization,balkanizations,balkanize,balkanized,balkanizes,balkanizing,barukhzy,bashibazouk,bazooka,bazookaman,bazookamen,bazookas,bazouki,bazoukis.berkowitz.blitzkrieg,blitzkrieged,blitzkrieging,blitzkriegs,blksize.bouzouk... 查看详情