Go to diff to previous submission
#include <iostream> #include <cstdlib> #include <cstdio> #include <vector> #include <algorithm> #include <cmath> #include <climits> typedef unsigned int uint; typedef long double number; struct point { number x, y; point(): x(0.0), y(0.0) { } point(number x, number y): x(x), y(y) { } }; bool operator== (const point& a, const point& b) { return a.x == b.x && a.y == b.y; } bool operator!= (const point& a, const point& b) { return a.x != b.x || a.y != b.y; } bool operator< (const point& a, const point& b) { return a.x == b.x ? a.y < b.y : a.x < b.x; } bool operator> (const point& a, const point& b) { return a.x == b.x ? a.y > b.y : a.x > b.x; } number cross(const point& a, const point& b, const point& c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } number dist(const point& a, const point& b) { number dx = b.x - a.x; number dy = b.y - a.y; if (dx == 0.0 && dy == 0.0) return 0.0; return sqrt( dx * dx + dy * dy ); } point center(const point& p1, const point& p2, const point& far) { if (p1.x == p2.x) return point(p1.x, far.y); if (p1.y == p2.y) return point(far.x, p1.y); number k = (p2.y - p1.y) / (p2.x - p1.x); number kperp = (p1.x - p2.x) / (p2.y - p1.y); number d = p2.y - k * p2.x; number dperp = far.y - kperp * far.x; number xint = (d - dperp) / (kperp - k); number yint = kperp * xint + dperp; return point(xint, yint); } void obtainconvexhull(std::vector<point>& hull, std::vector<point>& points) { std::sort(points.begin(), points.end()); hull.push_back(points[0]); uint last_added = 0; uint ref; do { ref = 0; for (uint j = 0; j < points.size(); j++) { int wedge = cross(hull[last_added], points[ref], points[j]); if (points[ref] == hull[last_added] || wedge < 0) ref = j; } if (ref != 0) { hull.push_back(points[ref]); points.erase(points.begin()+ref); last_added++; } } while (ref != 0); } number getminwidth(std::vector<point>& polygon) { uint aux = polygon.size(); number minwidthoverall = INT_MAX; // WHAT? point firstmaxc; bool is_firstmaxc = false; for (uint i = 0; i < aux; i++) { number maxwidthforoneside = 0.0; point maxc; if (is_firstmaxc && polygon[i] == firstmaxc) break; point lineA = polygon[i]; point lineB = polygon[(i + 1) % aux]; for (uint j = 0; j < aux; j++) if (polygon[j] != lineA && polygon[j] != lineB) { point c = center(lineA, lineB, polygon[j]); number d = dist(c, polygon[j]); //~ if (d > 21213212) //~ printf("bad: c.x=%Lf, c.y=%Lf, pol[j].x=%Lf, pol[j].y=%Lf\n", c.x, c.y, polygon[j].x, polygon[j].y); if (maxwidthforoneside < d) { maxwidthforoneside = d; maxc = polygon[j]; } } if (!is_firstmaxc) firstmaxc = maxc; number left = 0.0; // product < 0 number right = 0.0; // product > 0 point ab = center(lineA, lineB, maxc); for (uint j = 0; j < aux; j++) { if (maxc == polygon[j]) continue; point c = center(maxc, ab, polygon[j]); number d = dist(c, polygon[j]); number product = cross(maxc, ab, polygon[j]); if (product < 0) left = std::max(left, d); if (product > 0) right = std::max(right, d); } //~ printf("current minwidth: %Lf\n", minwidthoverall); //~ printf("maxwidthforoneside: %Lf, left: %Lf, right: %Lf\n", maxwidthforoneside, left, right); minwidthoverall = std::min(minwidthoverall, maxwidthforoneside * 2 + (left + right) * 2); //~ printf("new minwidth: %Lf\n\n", minwidthoverall); } return minwidthoverall; } int main() { int vertices; while (true) { if (1 != scanf("%d", &vertices)) break; std::vector<point> polygon; while (vertices--) { int x, y; scanf("%d %d", &x, &y); polygon.push_back(point(number(x), number(y))); } std::vector<point> convexhull; obtainconvexhull(convexhull, polygon); number answertoeverything = getminwidth(convexhull); printf("%Lf\n", answertoeverything); } return 0; }
--- c5.s900.cteam063.fo.cpp.0.fo.cpp +++ c5.s907.cteam063.fo.cpp.0.fo.cpp @@ -96,8 +96,14 @@ uint aux = polygon.size(); number minwidthoverall = INT_MAX; // WHAT? + point firstmaxc; + bool is_firstmaxc = false; for (uint i = 0; i < aux; i++) { number maxwidthforoneside = 0.0; point maxc; + + if (is_firstmaxc && polygon[i] == firstmaxc) + break; + point lineA = polygon[i]; point lineB = polygon[(i + 1) % aux]; @@ -116,4 +122,6 @@ } } + if (!is_firstmaxc) + firstmaxc = maxc; number left = 0.0; // product < 0