Source code for submission s940

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;
}
 

Diff to submission s904

--- 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);
         }