Source code for submission s972

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 10e-8
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=40000,xmax=-40000,ymin=40000,ymax=-40000;
	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) > 10e-9) {
		double ang = (l+r)/2.0;
		ans = min(ans, calc(ang));
		if(calc(ang) >= calc(ang-eps)-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, calc(45));
		ans = min(ans, solve(45, 90));
		ans = min(ans, calc(90));
		ans = min(ans, solve(90, 135));
		ans = min(ans, calc(135));
		ans = min(ans, solve(135, 180));
 
		printf("%.6lf\n", ans);
	}
	return 0;
}
 

Diff to submission s953

--- c5.s953.cteam042.fo.cpp.0.fo-binsearch.cpp
+++ c5.s972.cteam042.fo.cpp.0.fo-binsearch.cpp
@@ -17,5 +17,5 @@
                 YY[i] = L[i]*sin(Q[i]+ang*M_PI/180);
         }
-        double xmin=20000,xmax=-20000,ymin=20000,ymax=-20000;
+        double xmin=40000,xmax=-40000,ymin=40000,ymax=-40000;
         REP(i, N) {
                 xmin = min(XX[i], xmin);
@@ -32,5 +32,5 @@
                 double ang = (l+r)/2.0;
                 ans = min(ans, calc(ang));
-                if(calc(ang+eps) > calc(ang-eps)-eps) {
+                if(calc(ang) >= calc(ang-eps)-eps) {
                         r = ang;
                 } else l = ang;
@@ -48,6 +48,9 @@
                 }
                 ans = min(ans, solve(0, 45));
+                ans = min(ans, calc(45));
                 ans = min(ans, solve(45, 90));
+                ans = min(ans, calc(90));
                 ans = min(ans, solve(90, 135));
+                ans = min(ans, calc(135));
                 ans = min(ans, solve(135, 180));