Go to diff to previous submission
#include <iostream> #include <set> #include <stdio.h> #include <utility> #include <map> #include <string> #include <sstream> #include <algorithm> #include <iterator> #include <vector> #include <cmath> using namespace std; typedef pair<int,int> point; typedef vector<pair<int,int> >::iterator vp_it; bool counterclockwise(const point &A, const point &B, const point &C) { return ((B.first - A.first)*(C.second-A.second)-(B.second-A.second)*(C.first-A.first)) > 0; } bool clockwise(const point &A, const point &B, const point &C) { return ((B.first - A.first)*(C.second-A.second)-(B.second-A.second)*(C.first-A.first)) < 0; } double distance(const point &A, const point &B, const point &C) { return ((B.first - A.first)*(C.second - A.second) - (C.first - A.first)*(B.second -A.second)) / sqrt((B.first - A.first)*(B.first - A.first) + (B.second - A.second)*(B.second - A.second)); } point normpoint(const point &A, const point &B) { point x = make_pair(B.first - A.first, B.second - A.second); point nx = make_pair(-x.second, x.first); return nx; } point add(const point &A, const point &B) { return make_pair(A.first + B.first, A.second + B.second); } bool EQ(double a, double b) { if (abs(a-b) < 1e-9) return true; return false; } vector<point> convex_hull(vector<point> &Ps) { sort(Ps.begin(),Ps.end()); if (Ps.size() < 3) return Ps; vector<point> lower,upper; lower.push_back(Ps.front()); upper.push_back(Ps.front()); for (vp_it p_it = Ps.begin()+1;p_it != Ps.end(); ++p_it) { vp_it it = lower.end()-1; for (;it != lower.begin();--it) if (it == lower.begin() || counterclockwise(*(it-1),*it,*p_it)) break; lower.erase(it+1,lower.end()); lower.push_back(*p_it); it = upper.end()-1; for (;it != upper.begin();--it) if (it == upper.begin() || clockwise(*(it-1),*it,*p_it)) break; upper.erase(it+1,upper.end()); upper.push_back(*p_it); } upper.pop_back(); reverse(upper.begin(),upper.end()); upper.pop_back(); for (int i = 0; i < upper.size(); ++i) lower.push_back(upper[i]); return lower; } int main(){ int N; //point np = add(make_pair(1,1), normpoint(make_pair(0,0),make_pair(1,0))); //cout << np.first << " " << np.second << "\n"; //return 0; while (cin >> N) { vector<point> points; int x,y; for (int i = 0; i < N; ++i) { cin >> x >> y; points.push_back(make_pair(x,y)); } vector<point> conv_hull = convex_hull(points); int ri,ui,li; ui = 2; li = 0; ri = 1; double mcir = 14e20; for (int i = 0; i < conv_hull.size(); i++) { point a = conv_hull[i]; point b = conv_hull[(i+1)%conv_hull.size()]; double maxd = -14e20; for (int j = (ui)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) { if (!EQ(distance(a,b,conv_hull[j]),maxd) && distance(a, b, conv_hull[j]) < maxd) break; maxd = distance(a,b,conv_hull[j]); ui = j; } point np = normpoint(a,b); maxd = 14e20; for (int j = (ri)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) { if (!EQ(distance(b,add(b,np),conv_hull[j]),maxd) && distance(b, add(b,np), conv_hull[j]) > maxd) break; maxd = distance(b, add(b,np),conv_hull[j]); ri = j; } maxd = -14e20; if (i == 0) li = ui; for (int j = (li)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) { if (!EQ(distance(b,add(b,np),conv_hull[j]),maxd) && distance(b, add(b,np), conv_hull[j]) < maxd) break; maxd = distance(b, add(b,np),conv_hull[j]); li = j; } double cir = 2*abs(distance(a,b,conv_hull[ui])) + 2*(abs(distance(b,add(b,np),conv_hull[li])) + abs(distance(b,add(b,np),conv_hull[ri]))); mcir = min(mcir, cir); } cout << mcir << "\n"; } return 0; }
--- c5.s1061.cteam026.fo.cpp.0.fo.cpp +++ c5.s1110.cteam026.fo.cpp.0.fo.cpp @@ -39,5 +39,5 @@ bool EQ(double a, double b) { - if (abs(a-b) < 10e-6) return true; + if (abs(a-b) < 1e-9) return true; return false; } @@ -93,10 +93,10 @@ li = 0; ri = 1; - double mcir = 14e9; + double mcir = 14e20; for (int i = 0; i < conv_hull.size(); i++) { point a = conv_hull[i]; point b = conv_hull[(i+1)%conv_hull.size()]; - double maxd = -14e9; + double maxd = -14e20; for (int j = (ui)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) { if (!EQ(distance(a,b,conv_hull[j]),maxd) && distance(a, b, conv_hull[j]) < maxd) @@ -107,5 +107,5 @@ point np = normpoint(a,b); - maxd = 14e9; + maxd = 14e20; for (int j = (ri)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) { if (!EQ(distance(b,add(b,np),conv_hull[j]),maxd) && distance(b, add(b,np), conv_hull[j]) > maxd) @@ -114,5 +114,5 @@ ri = j; } - maxd = -14e9; + maxd = -14e20; if (i == 0) li = ui; for (int j = (li)%conv_hull.size(); ; j = (j+1)%conv_hull.size()) {