Source code for submission s953

Go to diff to previous submission

fo-binsearch.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <algorithm>
  4. using namespace std;
  5. #include <math.h>
  6. #define REP(A,B) for(int A=0; A<B;A++)
  7. #define eps 10e-8
  8. int X[11111], Y[11111];
  9. double XX[11111], YY[11111];
  10. double Q[11111];
  11. double L[11111];
  12. int N;
  13.  
  14. double calc(double ang) {
  15. REP(i, N) {
  16. XX[i] = L[i]*cos(Q[i]+ang*M_PI/180);
  17. YY[i] = L[i]*sin(Q[i]+ang*M_PI/180);
  18. }
  19. double xmin=20000,xmax=-20000,ymin=20000,ymax=-20000;
  20. REP(i, N) {
  21. xmin = min(XX[i], xmin);
  22. xmax = max(XX[i], xmax);
  23. ymin = min(YY[i], ymin);
  24. ymax = max(YY[i], ymax);
  25. }
  26. return 2*(xmax-xmin+ymax-ymin);
  27. }
  28.  
  29. double solve(double l, double r) {
  30. double ans = 10e12;
  31. while(fabs(l-r) > 10e-9) {
  32. double ang = (l+r)/2.0;
  33. ans = min(ans, calc(ang));
  34. if(calc(ang+eps) > calc(ang-eps)-eps) {
  35. r = ang;
  36. } else l = ang;
  37. }
  38. return ans;
  39. }
  40.  
  41. int main() {
  42. while(scanf("%d", &N) == 1) {
  43. double ans = 10e12;
  44. REP(i, N) {
  45. scanf("%d %d", X+i, Y+i);
  46. L[i] = sqrt((double)X[i]*X[i]+(double)Y[i]*Y[i]);
  47. Q[i] = atan2(Y[i], X[i]);
  48. }
  49. ans = min(ans, solve(0, 45));
  50. ans = min(ans, solve(45, 90));
  51. ans = min(ans, solve(90, 135));
  52. ans = min(ans, solve(135, 180));
  53.  
  54. printf("%.6lf\n", ans);
  55. }
  56. return 0;
  57. }
  58.  

Diff to submission s948

fo-binsearch.cpp

--- c5.s948.cteam042.fo.cpp.0.fo-binsearch.cpp
+++ c5.s953.cteam042.fo.cpp.0.fo-binsearch.cpp
@@ -5,5 +5,5 @@
 #include <math.h>
 #define REP(A,B) for(int A=0; A<B;A++)
-#define eps 10e-7
+#define eps 10e-8
 int X[11111], Y[11111];
 double XX[11111], YY[11111];
@@ -29,8 +29,8 @@
 double solve(double l, double r) {
         double ans = 10e12;
-        while(fabs(l-r) > 10e-8) {
+        while(fabs(l-r) > 10e-9) {
                 double ang = (l+r)/2.0;
                 ans = min(ans, calc(ang));
-                if(calc(ang+eps) > calc(ang-eps)) {
+                if(calc(ang+eps) > calc(ang-eps)-eps) {
                         r = ang;
                 } else l = ang;
@@ -49,4 +49,6 @@
                 ans = min(ans, solve(0, 45));
                 ans = min(ans, solve(45, 90));
+                ans = min(ans, solve(90, 135));
+                ans = min(ans, solve(135, 180));
 
                 printf("%.6lf\n", ans);