| 9 | return abs(imag(a) - imag(b)) > EPS ? |
| 10 | imag(a) < imag(b) : real(a) < real(b); } }; |
| 11 | double closest_pair(vector<point> pts) { |
| 12 | sort(pts.begin(), pts.end(), cmpx()); |
| 13 | set<point, cmpy> cur; |
| 14 | set<point, cmpy>::const_iterator it, jt; |
| 15 | double mn = INFINITY; |
| 16 | for (int i = 0, l = 0; i < size(pts); i++) { |
| 17 | while (real(pts[i]) - real(pts[l]) > mn) |
| 18 | cur.erase(pts[l++]); |
| 19 | it = cur.lower_bound(point(-INFINITY, imag(pts[i]) - mn)); |
| 20 | jt = cur.upper_bound(point(INFINITY, imag(pts[i]) + mn)); |
| 21 | while (it != jt) mn = min(mn, abs(*it - pts[i])), it++; |
| 22 | cur.insert(pts[i]); } |
| 23 | return mn; } |
| 24 | // vim: cc=60 ts=2 sts=2 sw=2: |