Go to diff to previous submission
#include <stdio.h> #include <stdlib.h> #include <algorithm> using namespace std; #include <math.h> #define REP(A,B) for(int A=0; A<B;A++) #define eps 0.00005 int X[11111], Y[11111]; double XX[11111], YY[11111]; double Q[11111]; double L[11111]; int N; double calc(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=20000,xmax=-20000,ymin=20000,ymax=-20000; REP(i, N) { xmin = min(XX[i], xmin); xmax = max(XX[i], xmax); ymin = min(YY[i], ymin); ymax = max(YY[i], ymax); } return 2*(xmax-xmin+ymax-ymin); } double solve(double l, double r) { double ans = 10e12; while(fabs(l-r) > 0.00005) { double ang = (l+r)/2.0; ans = min(ans, calc(ang)); if(calc(ang+eps) > calc(ang-eps)) { r = ang; } else l = ang; } return ans; } int main() { while(scanf("%d", &N) == 1) { 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]); Q[i] = atan2(Y[i], X[i]); } ans = min(ans, solve(0, 45)); ans = min(ans, solve(45, 90)); printf("%.6lf\n", ans); } return 0; }
--- c5.s904.cteam042.fo.cpp.0.fo.cpp +++ c5.s940.cteam042.fo.cpp.0.fo-binsearch.cpp @@ -5,10 +5,39 @@ #include <math.h> #define REP(A,B) for(int A=0; A<B;A++) +#define eps 0.00005 int X[11111], Y[11111]; double XX[11111], YY[11111]; double Q[11111]; double L[11111]; +int N; + +double calc(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=20000,xmax=-20000,ymin=20000,ymax=-20000; + REP(i, N) { + xmin = min(XX[i], xmin); + xmax = max(XX[i], xmax); + ymin = min(YY[i], ymin); + ymax = max(YY[i], ymax); + } + return 2*(xmax-xmin+ymax-ymin); +} + +double solve(double l, double r) { + double ans = 10e12; + while(fabs(l-r) > 0.00005) { + double ang = (l+r)/2.0; + ans = min(ans, calc(ang)); + if(calc(ang+eps) > calc(ang-eps)) { + r = ang; + } else l = ang; + } + return ans; +} + int main() { - int N; while(scanf("%d", &N) == 1) { double ans = 10e12; @@ -18,24 +47,7 @@ Q[i] = atan2(Y[i], X[i]); } + ans = min(ans, solve(0, 45)); + ans = min(ans, solve(45, 90)); - for(double ang = -180; ang < 180; ang+=0.5) { - 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=20000,xmax=-20000,ymin=20000,ymax=-20000; - REP(i, N) { - xmin = min(XX[i], xmin); - xmax = max(XX[i], xmax); - ymin = min(YY[i], ymin); - ymax = max(YY[i], ymax); - } - double curr = 2*(xmax-xmin+ymax-ymin); - if(curr < ans) { - ans = curr; - //printf("%lf\n", ang); - } -// printf("for ang=%lf: %lf\n", ang, 2*(xmax-xmin+ymax-ymin)); - } printf("%.6lf\n", ans); }