@Apass_Jack/

GarlandAboveGround_cs108639

Java

No description

fork
loading
Files
  • Main.java
Main.java
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
import java.util.Arrays;

public class Main {
    static class Garland {
        int n; // n >=3
        double A;

        Garland(int n, double A) {
            this.n = n;
            this.A = A;
        }

        double height(double d, int k) {
            // A + ((-d) + (-d + 2 * (k - 2))) * (k - 1) / 2;
            return A + (-d + k - 2) * (k - 1);
        }

        double last_height(double d) {
            return A + (-d + n - 2) * (n - 1);
        }

        boolean hit_the_ground(double d) {
            int k = (int) (Math.floor(d / 2) + 2);
            return k >= n && last_height(d) < 0 ||
                    k < n && height(d, k) < 0;
        }

        static double precision = Math.pow(10, -7);

        double get_minimum_last_height() {
            if (A >= (n-1) * (n-2)) return 0;

            double L = 0;
            double R = A + 1;
            double B_L = last_height(L);
            double B_R = last_height(R);

            while (B_L - B_R > precision) {
                double mid = (L + R) / 2.0;
                if (hit_the_ground(mid)) {
                    R = mid;
                    B_R = last_height(R);
                } else {
                    L = mid;
                    B_L = last_height(L);
                }
            }

            return B_L;
        }

    }

    public static void main(String[] args) {
        Garland g1 = new Garland(8, 15);
        System.out.println(g1.get_minimum_last_height());
        Garland g2 = new Garland(692, 532.81);
        System.out.println(g2.get_minimum_last_height());
    }
}