FOJ 192. Fences

Algorithm

競程作業，2017 TOPC Problem E：FOJ-192

題目是要你算出大圓面積跟裡面的小多邊形面積的差
大圓直接算就好了
小多邊形的面積有點麻煩，要拿已知的條件去二分搜，猜出他的外接圓半徑
高級題解在這：https://hackmd.io/s/Hy6LFym_b

這題我超雷，因為 C 的 abs 是專屬整數用的
浮點數要用 fabs
但是 C++ 是通用
結果我自己跑都很正常但是送出去一直 WA
QQ

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
127
128
#include<stdio.h>
#include<math.h>
#include<iomanip>
#include<iostream>
#include<stdlib.h>
#define _USE_MATH_DEFINES
#define RNAGE 1e-9

int main(){
  int t, n;
  std::cin>>t;
  // scanf("%d", &t);
  while(t--){
    double c, L, R, M, Max, tal, big;
    double ll[10010];
    bool flag;

    flag = 0;
    big = 0;
    std::cin>>c>>n;
    // scanf("%lf%d", &c, &n);
    for(int i=0; i<n; i++){
      std::cin>>ll[i];
      // scanf("%lf", &ll[i]);
      if(ll[i]>big) big = ll[i];
    }
    L = big/2;
    R = c;
    // int k=1000;

    Max = -1;
    tal = 0;
    M = big/2;
    double dtmp;
    for(int i=0; i<n; i++){
      dtmp = asin(ll[i]/(2*M))*2;
      // l[i] = acos((2*M*M - ll[i]*ll[i])/(2*M*M));
      // printf("%f ", (2*M*M - ll[i]*ll[i])/(2*M*M));
      if (dtmp>Max) Max = dtmp;
      tal += dtmp;
    }
    if(fabs(tal-Max*2-0.0)<RNAGE){
      M = M;
//      std::cout<<tal<<" "<<Max<<" "<<abs(tal-Max*2)<<"\n";
    }
    else if(tal-Max*2<0){
      while(1){
        flag = 1;
        // printf("up\n");
        M = (L + R)/2;
        Max = 0;
        tal = 0;
        double dtmp;
        // printf("MMMMM::::%f\n", M);
        for(int i=0; i<n; i++){

          dtmp = asin(ll[i]/(2*M))*2;
          // l[i] = acos((2*M*M - ll[i]*ll[i])/(2*M*M));
          // printf("%f ", (2*M*M - ll[i]*ll[i])/(2*M*M));
          if (dtmp>Max) Max = dtmp;
          tal += dtmp;
        }
        tal-=Max;
        // printf("\n");
        // printf("%f %f %f %f %f %f\n",l[0], l[1], l[2], Max, tal, tal-Max);
        // now = tal-Max;
        if(fabs(tal-Max)<=RNAGE) break;
        else if(tal-Max>RNAGE){
          // printf("kkkkk\n");
          R = M;
        }
        else if(tal-Max<-RNAGE){
          // printf("jizz\n");
          L = M;
        }
      }
    }
    // else if(tal-Max*2>0){
    else{
      while(1){
        M = (L + R)/2;
        Max = 0;
        tal = 0;
        double dtmp;
        // printf("MMMMM::::%f\n", M);
        for(int i=0; i<n; i++){
          dtmp = asin(ll[i]/(2*M))*2;
          // l[i] = acos((2*M*M - ll[i]*ll[i])/(2*M*M));
          // printf("%f ", (2*M*M - ll[i]*ll[i])/(2*M*M));
          if (dtmp>Max) Max = dtmp;
          tal += dtmp;
        }
        // printf("\n");
        // printf("%f %f %f %f %f %f\n",l[0], l[1], l[2], Max, tal, tal-Max);

        if((tal-2*M_PI)<-RNAGE){
          R = M;
        }
        else if((tal-2*M_PI)>RNAGE){
          // printf("jizz");
          L = M;
        }
        else break;
      }
    }

    // printf("%f %f %f %f %f\n", Max, tal, l[0], l[1], l[2]);

    double bigO = (c/M_PI/2)*(c/M_PI/2)*M_PI;
    double smallO = 0;
    double s;

    for(int i=0; i<n; i++){
      s = (M+M+ll[i])/2;
      smallO+=sqrt(s*(s-M)*(s-M)*(s-ll[i]));
    }
    if(flag){
      s = (M+M+big)/2;
      smallO-=sqrt(s*(s-M)*(s-M)*(s-big));
      smallO-=sqrt(s*(s-M)*(s-M)*(s-big));
    }
    // printf("%lf\n", smallO);
    // printf("%lf\n", M);
    // printf("%lf\n", bigO-smallO);
//    std::cout<<M<<"\n";
    std::cout<<std::setprecision(15)<<bigO-smallO<<"\n";
  }
}