BZOJ1337 最小圆覆盖

原题戳这里

题意

给你n个点,求最小的半径的圆覆盖这n个点

吐槽

​ 这题只有1个数据点,而且n=10,所以直接puts就行了

1
2
3
4
5
#include<cstdio>
using namespace std;
int main(){
puts("48.770");
}

下面是数据

10

24.4 57.4

71.7 99

85.4 78.6

70.6 39.2

35.3 8.9

14.8 77.6

2.3 50

14.1 84.9

99.3 49.6

47.8 43

好吧,这题貌似叫做随机增量法??

大概就是暴力枚举一个点,不行用两个点,还不行三个点,然后这样期望复杂度是O(n)O(n)

其实我就是来贴个计算几何模板的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
#include<cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f,oo = inf;
#define pi 3.14159265358979323846
#define IL inline
#define RG register
#define rep(i,a,b) for(RG int i=(a);i<(b);++i)
#define Rep(i,a,b) for(RG int i=(a);i<=(b);++i)
#define Dep(i,a,b) for(RG int i=(a);i>=(b);--i)
#define pc putchar
#define gc getchar
IL ll read(){
RG ll x=0;char f=0;RG char c=gc();
for(;!isdigit(c);c=gc())f|=(c=='-');
for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
IL double readdb(){
RG double x=0,p=0.1;RG char f=0,c=gc();
for(;!isdigit(c);c=gc())f|=(c=='-');
for(;isdigit(c);c=gc())x=x*10+(c^48);
if(c=='.')for(c=gc();isdigit(c);c=gc(),p/=10)x=x+(c^48)*p;
return f?-x:x;
}
IL void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);pc(x%10+'0');}
IL void writeln(ll x){write(x);puts("");}
IL void writeln(ll x,char c,ll y){write(x);pc(c);writeln(y);}
IL void writeln(ll x,char c,ll y,char d,ll z){write(x);pc(c);write(y);pc(d);writeln(z);}
#define debug(x) printf(#x" = %d\n",x);
#define rd() read()
#define rdb() readdb()
#define mem(x,v) memset(x,v,sizeof(x))
#define pb push_back
#define mp make_pair
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-(x)))
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define y1 ____y1
#define hash __hash
#define union _union
#define ramdom ((double)rand() / RAND_MAX)
#define x first
#define y second
const double eps = 1e-8;
int dcmp(double x){if(fabs(x) < eps) return 0;return x<0?-1:1;}
struct Point{
double x,y;
Point(double x=0,double y=0):x(x),y(y){};
Point operator + (const Point &a)const{return Point(x+a.x,y+a.y);}
Point operator - (const Point &a)const{return Point(x-a.x,y-a.y);}
Point operator * (double a){return Point(x*a,y*a);}
Point operator / (double a){return Point(x/a,y/a);}
void out(){
printf("{%.3lf,%.3lf}",x,y);
}
};
typedef Point Vector;
double cross(Point a,Point b){return a.x*b.y-b.x*a.y;}
double dot(Point a,Point b){return a.x*b.x+a.y*b.y;}
double dist(Point a,Point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
Point rotate(Vector a,double rad){
return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));
}//向量绕原点旋转rad度
struct Line{
Point x,y;
Line(Point x,Point y):x(x),y(y){}
void out(){
pc('[');x.out();y.out();pc(']');
}
};
typedef Line Segment;
Point Line_jiao(Line a,Line b){
double r1 = cross(a.x-b.x,b.y-b.x),r2 = cross(b.y-b.x,a.y-b.x);
return a.x+(a.y-a.x)*r1/(r1+r2);
}//给出两条直线,求它们的交点
Point center(Point A,Point B,Point C){
Point p = (A+B) / 2;
Point q = (A+C) / 2;
if(dcmp(cross(p-C,A-C))==0){
if(dcmp(dist(A,B)+dist(B,C)-dist(A,C))==0) return (A+C)/2;
if(dcmp(dist(A,B)+dist(A,B)-dist(B,C))==0) return (B+C)/2;
if(dcmp(dist(A,C)+dist(B,C)-dist(A,B))==0) return (A+B)/2;
}
Point _p=p+Point(-(p-A).y,(p-A).x);
Point _q=q+Point(-(q-A).y,(q-A).x);
Point answ = Line_jiao(Line(p,_p),Line(q,_q));
return answ;
}//给定三个点,求一个点满足这个点到三个点的距离的最大值最小
const int maxn = 1e5+233;
Point p[maxn];int n;
double min_circle_cover(Point p[],int n){
srand((unsigned long long)"Wzp Ak All OI contests");
random_shuffle(p,p+n);
double r = 0;
Point c = p[0];
rep(i,1,n){
if(dcmp(dist(p[i],c) - r) > 0){
c = p[i];r = 0;//够不到(逃
rep(j,0,i){
if(dcmp(dist(p[j],c)-r)>0){
c = (p[i]+p[j])/2;r = dist(p[i],c);
rep(k,0,j){
if(dcmp(dist(p[k],c)-r)>0){
c = center(p[i],p[j],p[k]);
r = dist(p[i],c);
}
}
}
}
}
}
return r;
}//给定n个点,求它们的最小圆覆盖的半径
int main(){
n = rd();
rep(i,0,n)
p[i].x=rdb(),p[i].y=rdb();
printf("%.3lf\n",min_circle_cover());
return 0;
}

突然想开个坑来填模板

文章目录
  1. 1. 题意
  2. 2. 吐槽