Source code for submission s1021

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-6
int X[11111], Y[11111];
long double XX[11111], YY[11111];
long double Q[11111];
long double L[11111];
int N;
 
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);
	}
	long 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);
}
 
long double solve(long double l, long double r) {
	long double ans = 10e12;
	while(fabs(l-r) > eps) {
//		printf("%Lf %Lf\n", l, r);
		long double first = l+(r-l)/3.0;
		long double sec = l+2*(r-l)/3.0;
		ans = min(ans, calc(first));
		ans = min(ans, calc(sec));
		if(calc(sec) >= calc(first)-eps) {
			r = sec;
		} else l = first;
	}
	return ans;
}
 
int main() {
	while(scanf("%d", &N) == 1) {
		long double ans = 10e12;
		REP(i, N) {
			scanf("%d %d", X+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]);
		}
		ans = min(ans, solve(0, 45));
		ans = min(ans, calc(45));
		ans = min(ans, solve(45, 90));
 
		printf("%.6Lf\n", ans);
	}
	return 0;
}
 

Diff to submission s988

--- c5.s988.cteam042.fo.cpp.0.fo-binsearch.cpp
+++ c5.s1021.cteam042.fo.cpp.0.fo-binsearch.cpp
@@ -30,9 +30,12 @@
         long double ans = 10e12;
         while(fabs(l-r) > eps) {
-                long double ang = (l+r)/2.0;
-                ans = min(ans, calc(ang));
-                if(calc(ang) >= calc(ang-eps)-eps) {
-                        r = ang;
-                } else l = ang;
+//              printf("%Lf %Lf\n", l, r);
+                long double first = l+(r-l)/3.0;
+                long double sec = l+2*(r-l)/3.0;
+                ans = min(ans, calc(first));
+                ans = min(ans, calc(sec));
+                if(calc(sec) >= calc(first)-eps) {
+                        r = sec;
+                } else l = first;
         }
         return ans;
@@ -50,8 +53,4 @@
                 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);