fork download
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. #define islld 1
  5. const double INF = 1e9;
  6. const double EPS = 1e-5;
  7. const double PI = acos(-1);
  8.  
  9. template<class T>
  10. class Point
  11. {
  12. public:
  13. union
  14. {
  15. struct
  16. {
  17. T x,y;
  18. };
  19. T data[2];
  20. };
  21. Point():x(0),y(0){}
  22. Point(T x,T y):x(x),y(y)
  23. {
  24.  
  25. }
  26. Point(T s):x(s),y(s){}
  27. template<typename T1>
  28. Point(const Point<T1>& p):x(p.x),y(p.y){}
  29.  
  30. void readInt32(){
  31. scanf("%d%d",&x,&y);
  32. }
  33. void readInt64(){
  34. #if islld
  35. scanf("%lld%lld",&x,&y);
  36. #else
  37. scanf("%I64d%I64d",&x,&y);
  38. #endif
  39. }
  40. void readfloat(){
  41. scanf("%f%f",&x,&y);
  42. }
  43. void readLongDouble(){
  44. scanf("%Lf%Lf",&x,&y);
  45. }
  46. void readDouble(){
  47. scanf("%lf%lf",&x,&y);
  48. }
  49. template<typename T1>
  50. bool operator==(const Point<T1>& rhs)
  51. {
  52. auto v = *this-rhs;
  53. return fabs(v.x) <= EPS && fabs(v.y) <= EPS;
  54. }
  55. inline friend Point operator+(const Point& lhs, const Point& rhs) { return Point(lhs.x+rhs.x,lhs.y+rhs.y); }
  56. inline friend Point operator-(const Point& lhs, const Point& rhs) { return Point(lhs.x-rhs.x,lhs.y-rhs.y); }
  57. inline friend Point operator*(const Point& lhs, const Point& rhs) { return Point(lhs.x*rhs.x,lhs.y*rhs.y); }
  58. inline friend Point operator/(const Point& lhs, const Point& rhs) { return Point(lhs.x/rhs.x,lhs.y/rhs.y); }
  59. };
  60. template<typename T>
  61. inline T cross(const Point<T>& v1,const Point<T>& v2)
  62. {
  63. return v1.x*v2.y-v1.y*v2.x;
  64. }
  65. template<typename T>
  66. inline T dot(const Point<T>& v1,const Point<T>& v2)
  67. {
  68. return v1.x*v2.x+v1.y*v2.y;
  69. }
  70. template<typename T>
  71. inline T sqlen(const Point<T>& p)
  72. {
  73. return p.x*p.x+p.y*p.y;
  74. }
  75. template<typename T>
  76. struct cmp_x {
  77. bool operator()(const Point<T> & a, const Point<T> & b) {
  78. return a.x < b.x || a.x == b.x && a.y < b.y;
  79. }
  80. };
  81. template<typename T>
  82. struct cmp_y {
  83. bool operator()(const Point<T> & a, const Point<T> & b)const {
  84. return a.y < b.y || a.y == b.y && a.x < b.x ;
  85. }
  86. };
  87.  
  88. template<typename T>
  89. pair<pair<Point<T>,Point<T>>,T> closest_pair(vector<Point<T>> & points)
  90. {
  91. T d = INF;
  92. T ds = INF;
  93. Point<T> p1,p2;
  94. sort(points.begin(),points.end(),cmp_x<T>());
  95. set<Point<T>, cmp_y<T> > w;
  96. for(int i=0;i<points.size();i++){
  97. auto it = w.lower_bound(Point<ll>(-INF,points[i].y-ds));
  98. while(it != w.end() && abs(points[i].y-it->y) <= ds){
  99. auto itc = it;
  100. it++;
  101. if(abs(points[i].x - itc->x) > d){
  102. w.erase(itc);
  103. }
  104. else{
  105. T di = sqlen(points[i]-*itc);
  106. if(d > di){
  107. d =di;
  108. ds = sqrt(d)+1;
  109. p1 = points[i];
  110. p2 = *itc;
  111. }
  112. }
  113. }
  114. w.insert(points[i]);
  115. }
  116. return make_pair(make_pair(p1,p2),d);
  117. }
  118.  
  119. int main()
  120. {
  121. int n;
  122.  
  123. vector<Point<double>> ps;
  124. while(true)
  125. {
  126. scanf("%d",&n);
  127. if(n==0)
  128. break;
  129. ps.clear();
  130. ps.reserve(n);
  131. for(int i=0;i<n;i++)
  132. {
  133. Point<double> p;p.readDouble();
  134. ps.push_back(p);
  135. }
  136. double ans = 10000;
  137. double d = closest_pair<double>(ps).second;
  138. ans = min(ans,sqrt((double)d));
  139. if(ans >= 10000.0-EPS)
  140. puts("INFINITY");
  141. else
  142. printf("%.4f\n",ans);
  143. }
  144. return 0;
  145. }
  146.  
Time limit exceeded #stdin #stdout 5s 15760KB
stdin
Standard input is empty
stdout
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0.0000
0