题目:点击打开链接
题意:最小球覆盖裸题。
分析:三分套三分再套三分(x,y,z三个方向嵌套三分)或者模拟退火。
代码一(三分):
复制代码
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#include<algorithm> #include<iostream> #include<fstream> #include<complex> #include<cstdlib> #include<cstring> #include<cassert> #include<iomanip> #include<string> #include<cstdio> #include<bitset> #include<vector> #include<cctype> #include<cmath> #include<ctime> #include<stack> #include<queue> #include<deque> #include<list> #include<set> #include<map> using namespace std; #define pt(a) cout<<a<<endl #define debug test #define mst(ss,b) memset((ss),(b),sizeof(ss)) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pii pair<int,int> #define fi first #define se second #define ll long long #define ull unsigned long long #define pb push_back #define mp make_pair #define inf 0x3f3f3f3f #define eps 1e-10 #define PI acos(-1.0) const ll mod = 1e9+7; const int N = 1e2+10; ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} int to[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; struct P{ double x,y,z; }p[N]; double dis(P A,P B){ return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)+(A.z-B.z)*(A.z-B.z)); } int n; double cal(double x,double y,double z) { double sum=0; for(int i=0;i<n;i++)sum=max(sum,dis(p[i],(P){x,y,z})); return sum; } double cal(double x,double y) { double l=-100000,r=100000,ans=1e18; for(int i=1;i<=50;i++) { double mid=(l+r)/2; double m=(mid+r)/2; double L=cal(x,y,mid); double R=cal(x,y,m); if(L>R)l=mid; else r=m; ans=min(ans,L); ans=min(ans,R); } return ans; } double cal(double x) { double l=-100000,r=100000,ans=1e18; for(int i=1;i<=50;i++) { double mid=(l+r)/2; double m=(mid+r)/2; double L=cal(x,mid); double R=cal(x,m); if(L>R)l=mid; else r=m; ans=min(ans,L); ans=min(ans,R); } return ans; } int main() { cin>>n; for(int i=0;i<n;i++)scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z); double l=-100000,r=100000,ans=1e18; for(int i=1;i<=50;i++) { double mid=(l+r)/2; double m=(mid+r)/2; double L=cal(mid); double R=cal(m); if(L>R)l=mid; else r=m; ans=min(ans,L); ans=min(ans,R); } printf("%.5fn",ans); return 0; }
代码二(退火法):
复制代码
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///#pragma comment(linker, "/STACK:102400000,102400000") ///#include<unordered_map> ///#include<unordered_set> #include<algorithm> #include<iostream> #include<fstream> #include<complex> #include<cstdlib> #include<cstring> #include<cassert> #include<iomanip> #include<string> #include<cstdio> #include<bitset> #include<vector> #include<cctype> #include<cmath> #include<ctime> #include<stack> #include<queue> #include<deque> #include<list> #include<set> #include<map> using namespace std; #define pt(a) cout<<a<<endl #define debug test #define mst(ss,b) memset((ss),(b),sizeof(ss)) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pii pair<int,int> #define fi first #define se second #define ll long long #define ull unsigned long long #define pb push_back #define mp make_pair #define inf 0x3f3f3f3f #define eps 1e-10 #define PI acos(-1.0) const ll mod = 1e9+7; const int N = 110; ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} int to[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int n; struct P{ double x,y,z; }s,p[N]; double delta,ans; double dis(P a,P b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z)); } void sa() { s.x=s.y=s.z=0; delta=10000,ans=1e20; ///delta开始要设大一点,不然会wa while(delta>eps) { int d=1; for(int i=2;i<=n;i++) if(dis(s,p[i])>dis(s,p[d])) d=i; double md=dis(s,p[d]); ans=min(ans,md); s.x+=(p[d].x-s.x)/md*delta; s.y+=(p[d].y-s.y)/md*delta; s.z+=(p[d].z-s.z)/md*delta; delta*=0.99; } cout<<fixed<<setprecision(7)<<ans<<endl; } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); while(cin>>n) { for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y>>p[i].z; sa(); } return 0; }
最后
以上就是无情皮带最近收集整理的关于2018 ACM-ICPC 南京站 D Country Meow的全部内容,更多相关2018内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复