#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class Point { public: int y, x; Point(){ y = x = 0; } Point(int y0, int x0){ y = y0; x = x0; } Point operator+(const Point& p) const{ return Point(y + p.y, x + p.x); } Point operator-(const Point& p) const{ return Point(y - p.y, x - p.x); } Point operator*(int a) const{ return Point(y * a, x * a); } int length2() const{ return y * y + x * x; } int dist2(const Point& p) const{ return (y - p.y) * (y - p.y) + (x - p.x) * (x - p.x); } int dot(const Point& p) const{ return y * p.y + x * p.x; // |a|*|b|*cosθ } int cross(const Point& p) const{ return x * p.y - y * p.x; // |a|*|b|*sinθ } }; void convexHull(const vector& p0, vector& cv) { class Compare{ public: bool operator()(const Point& a, const Point& b){ return a.x < b.x || (a.x == b.x && a.y < b.y); } }; vector p = p0; sort(p.begin(), p.end(), Compare()); int n = p.size(); int j = 0; cv.clear(); for(int i=0; i<2*n-1; ++i){ Point tmp = (i= 2 && (tmp-cv[j-2]).cross(cv[j-1]-cv[j-2]) < 0){ cv.pop_back(); -- j; } cv.push_back(tmp); ++ j; } cv.pop_back(); } int main() { int n; cin >> n; vector station(n); vector > > grid(2003, vector >(2003)); for(int i=0; i> x >> y; y += 10010; x += 10010; station[i].y = y; station[i].x = x; grid[y/10][x/10].push_back(i); } vector check(n, false); double ret = 2.0; for(int i=0; i q; q.push(i); vector select(1, station[i]); while(!q.empty()){ Point p = station[q.front()]; q.pop(); int y = p.y / 10; int x = p.x / 10; for(int i=0; i<9; ++i){ for(unsigned j=0; j cv; convexHull(select, cv); int m = cv.size(); int j = 0; for(int i=0; i