zoj 3716 Ribbon Gymnastics

本文从WordPress迁移而来, 查看全部WordPress迁移文章

二分答案

题意:给4个点,以这些点作为圆心画4个圆(4个圆大小不需要相同),不能出现重叠,设4个圆的半径为r1,r2,r3,r4,使得4个半径的和最大

1
2
3
4
5
6
7
r1 + r2 <= d12
r1 + r3 <= d13
r1 + r4 <= d14
r2 + r3 <= d23
r2 + r4 <= d24
r3 + r4 <= d34
sum = d12 + d13 + d14 + d23 + d24 + d34

上面式子相加

1
2
3 * r1 + 3 * r2 + 3 * r3 + 3 * r4 <= sum
r1 + r2 + r3 + r4 <= sum/3

然后二分枚举(r1 + r2 + r3 + r4),再检验,检验方法为

1
2
3
4
r1 + r2 + r3 + r4 = mid
(r1 + r2) + (r3 + r4) = mid <= d12 + d34
(r1 + r3) + (r2 + r4) = mid <= d13 + d24
(r1 + r4) + (r2 + r3) = mid <= d14 + d23

上面3个式子都成立,则检验mid是成功的

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const double EPS = 0.0000000001;

int cx[5],cy[5];
double sum,d[5][5];

inline double dis(int i,int j){
return sqrt(((double)cx[i]-(double)cx[j])*((double)cx[i]-(double)cx[j]) +
((double)cy[i]-(double)cy[j])*((double)cy[i]-(double)cy[j]));
}

bool check(double ans){
if(ans > d[1][2] + d[3][4]) return false;
if(ans > d[1][3] + d[2][4]) return false;
if(ans > d[1][4] + d[2][3]) return false;
return true;
}

int main(){
while(scanf("%d%d",&cx[1],&cy[1])!=EOF){
for(int i = 2; i <= 4; i++)
scanf("%d%d",&cx[i],&cy[i]);
double sum = 0;
for(int i = 1; i <= 4; i++)
for(int j = i+1; j <= 4; j++)
d[i][j] = dis(i,j) , sum += d[i][j];
/*
for(int i = 1; i <= 4; i++)
for(int j = i+1; j <= 4; j++)
printf("d[%d][%d] = %.8f\n",i,j,d[i][j]);
printf("sum = %.8f\n",sum);
*/
double low = 0;
double high = sum/3;
double ans = -1;
while(fabs(low - high) >= EPS){
double mid = (low + high) / 2;
if(check(mid)){
ans = mid; low = mid;
}
else high = mid;
}
printf("%.8f\n",ans);
}
return 0;
}