Go to diff to previous submission
#include <stdio.h> #include <stdlib.h> #include <map> #include <math.h> using namespace std; typedef map<double, double> MAP; typedef MAP::iterator IT; typedef struct POINT { int x; int y; } POINT; typedef struct DOINT { double x; double y; } DOINT; POINT Input[20000]; DOINT Point[20000]; double Queue[1000]; int n; double GetPerimeter(double d) { d *= (atan(1) * 4) / 180.; double xMin = 1e10, xMax = -1e10, yMin = 1e10, yMax = -1e10; for(int i = 0; i < n; i++) { double x = Input[i].x; double y = Input[i].y; Point[i].x = (cos(d) * x) - (sin(d) * y); Point[i].y = (sin(d) * x) + (cos(d) * y); if(Point[i].x < xMin) xMin = Point[i].x; if(Point[i].x > xMax) xMax = Point[i].x; if(Point[i].y < yMin) yMin = Point[i].y; if(Point[i].y > yMax) yMax = Point[i].y; } return 2. * ((xMax - xMin) + (yMax - yMin)); } int main() { while(scanf("%d", &n) > 0) { MAP Map; Map.clear(); double rsl; for(int i = 0; i < n; i++) { scanf("%d%d", &(Input[i].x), &(Input[i].y)); } double step = 90. / 1024.; for(double d = 0.; d <= 90.; d += step) { Map[GetPerimeter(d)] = d; } for(int k = 0; k < 20; k++) { step /= 8.; int i = 0; for(IT it = Map.begin(); i < 5; it++, i++) { Queue[i] = it->second; } Map.clear(); for(i = 0; i < 5; i++) { double d = Queue[i]; for(int j = -8; j <= 8; j++) { double dd = d + (j * step); Map[GetPerimeter(dd)] = dd; } } } /*for(IT it = Map.begin(); it != Map.end(); it++) { printf("%lf for %lf degrees\n", it->first, it->second); }*/ rsl = Map.begin()->first; printf("%lf\n", rsl); } return 0; }
--- c5.s1046.cteam091.fo.cpp.0.fo.cpp +++ c5.s1050.cteam091.fo.cpp.0.fo.cpp @@ -72,7 +72,7 @@ } - for(int k = 0; k < 10; k++) + for(int k = 0; k < 20; k++) { - step /= 64.; + step /= 8.; int i = 0; for(IT it = Map.begin(); i < 5; it++, i++) @@ -81,8 +81,10 @@ } + Map.clear(); + for(i = 0; i < 5; i++) { double d = Queue[i]; - for(int j = -64; j <= 64; j++) + for(int j = -8; j <= 8; j++) { double dd = d + (j * step);