Source code for submission s1136

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-6
  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) > eps) {
  32. // printf("%Lf %Lf\n", l, r);
  33. long double first = l+(r-l)/3.0;
  34. long double sec = l+2*(r-l)/3.0;
  35. ans = min(ans, calc(first));
  36. ans = min(ans, calc(sec));
  37. if(calc(sec) >= calc(first)-eps) {
  38. r = sec;
  39. } else l = first;
  40. }
  41. return ans;
  42. }
  43.  
  44. int main() {
  45. while(scanf("%d", &N) == 1) {
  46. long double ans = 10e12;
  47. REP(i, N) {
  48. scanf("%d %d", X+i, Y+i);
  49. L[i] = sqrt((long double)X[i]*X[i]+(long double)Y[i]*Y[i]);
  50. Q[i] = atan2(Y[i], X[i]);
  51. }
  52. double segs = 10;
  53. for(int i = 0; i < segs; i++) {
  54. ans = min(ans, solve(i*90/segs, (i+1)*(90/segs)));
  55. }
  56.  
  57. printf("%.6Lf\n", ans);
  58. }
  59. return 0;
  60. }
  61.  

Diff to submission s1021

fo-binsearch.cpp

--- c5.s1021.cteam042.fo.cpp.0.fo-binsearch.cpp
+++ c5.s1136.cteam042.fo.cpp.0.fo-binsearch.cpp
@@ -50,7 +50,8 @@
                         Q[i] = atan2(Y[i], X[i]);
                 }
-                ans = min(ans, solve(0, 45));
-                ans = min(ans, calc(45));
-                ans = min(ans, solve(45, 90));
+                double segs = 10;
+                for(int i = 0; i < segs; i++) {
+                        ans = min(ans, solve(i*90/segs, (i+1)*(90/segs)));
+                }
 
                 printf("%.6Lf\n", ans);