Source code for submission s985

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. long double XX[11111], YY[11111];
  10. long double Q[11111];
  11. long double L[11111];
  12. int N;
  13.  
  14. long double calc(long 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. long double xmin=40000,xmax=-40000,ymin=40000,ymax=-40000;
  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. long double solve(long double l, long double r) {
  30. long double ans = 10e12;
  31. while(fabs(l-r) > 10e-9) {
  32. long double ang = (l+r)/2.0;
  33. ans = min(ans, calc(ang));
  34. if(calc(ang) >= 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. long double ans = 10e12;
  44. REP(i, N) {
  45. scanf("%d %d", X+i, Y+i);
  46. L[i] = sqrt((long double)X[i]*X[i]+(long 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, calc(45));
  51. ans = min(ans, solve(45, 90));
  52. ans = min(ans, calc(90));
  53. ans = min(ans, solve(90, 135));
  54. ans = min(ans, calc(135));
  55. ans = min(ans, solve(135, 180));
  56.  
  57. printf("%.6Lf\n", ans);
  58. }
  59. return 0;
  60. }
  61.  

Diff to submission s972

fo-binsearch.cpp

--- c5.s972.cteam042.fo.cpp.0.fo-binsearch.cpp
+++ c5.s985.cteam042.fo.cpp.0.fo-binsearch.cpp
@@ -7,15 +7,15 @@
 #define eps 10e-8
 int X[11111], Y[11111];
-double XX[11111], YY[11111];
-double Q[11111];
-double L[11111];
+long double XX[11111], YY[11111];
+long double Q[11111];
+long double L[11111];
 int N;
 
-double calc(double ang) {
+long double calc(long double ang) {
         REP(i, N) {
                 XX[i] = L[i]*cos(Q[i]+ang*M_PI/180);
                 YY[i] = L[i]*sin(Q[i]+ang*M_PI/180);
         }
-        double xmin=40000,xmax=-40000,ymin=40000,ymax=-40000;
+        long double xmin=40000,xmax=-40000,ymin=40000,ymax=-40000;
         REP(i, N) {
                 xmin = min(XX[i], xmin);
@@ -27,8 +27,8 @@
 }
 
-double solve(double l, double r) {
-        double ans = 10e12;
+long double solve(long double l, long double r) {
+        long double ans = 10e12;
         while(fabs(l-r) > 10e-9) {
-                double ang = (l+r)/2.0;
+                long double ang = (l+r)/2.0;
                 ans = min(ans, calc(ang));
                 if(calc(ang) >= calc(ang-eps)-eps) {
@@ -41,8 +41,8 @@
 int main() {
         while(scanf("%d", &N) == 1) {
-                double ans = 10e12;
+                long double ans = 10e12;
                 REP(i, N) {
                         scanf("%d %d", X+i, Y+i);
-                        L[i] = sqrt((double)X[i]*X[i]+(double)Y[i]*Y[i]);
+                        L[i] = sqrt((long double)X[i]*X[i]+(long double)Y[i]*Y[i]);
                         Q[i] = atan2(Y[i], X[i]);
                 }
@@ -55,5 +55,5 @@
                 ans = min(ans, solve(135, 180));
 
-                printf("%.6lf\n", ans);
+                printf("%.6Lf\n", ans);
         }
         return 0;