#include using namespace std; typedef complex point; typedef pair dd; #define rep(i, a, b) for(auto i = (a); i < (b); ++i) const double EPS = 1e-9; struct kahan { double s, c; kahan(double _s) : s(_s), c(0.0) { } void add(double d) { s += d; /* No kahan :) double y = d - c; double t = s + y; c = (t - s) - y; s = t; */ } void mod(double d) { if(d > EPS && d < s) { c = 0; s = fmod(s, d); } } double get() { return s; } }; map ind, outer; double dot(point a, point b) { return real(conj(a) * b); } double cross(point a, point b) { return imag(conj(a) * b); } double ccw(point a, point b, point c) { return cross(b - a, c - b); } bool cmp(const point &a, const point &b) { return abs(real(a) - real(b)) > EPS ? real(a) < real(b) : imag(a) < imag(b); } vector convexhull(vector p) { int n = p.size(), l = 0; if(n <= 2) return p; sort(p.begin(), p.end(), cmp); vector hull(2 * n + 1); rep(i,0,n) { if (i > 0 && p[i] == p[i - 1]) continue; while (l >= 2 && ccw(hull[l - 2], hull[l - 1], p[i]) >= EPS) l--; hull[l++] = p[i]; } int r = l; for (int i = n - 2; i >= 0; i--) { if (p[i] == p[i + 1]) continue; while (r - l >= 1 && ccw(hull[r - 2], hull[r - 1], p[i]) >= EPS) r--; hull[r++] = p[i]; } hull.resize(l == 1 ? 1 : r - 1); reverse(hull.begin(), hull.end()); return hull; } void reduce_mod(vector &hull, kahan &d) { kahan sm(0.0); for(int j = 0; j < hull.size(); ++j) { int k = (j + 1) % hull.size(); sm.add(abs(hull[j] - hull[k])); } d.mod(sm.get()); } void move(int &i, vector &hull, vector &allpts, kahan &d) { while(hull.size() > 1) { int j = (i + 1) % hull.size(); if(abs(hull[i] - hull[j]) < d.get() + EPS) { d.add(-abs(hull[i] - hull[j])); i = j; return; } vector filter_pts; for(int k = 0; k < allpts.size(); ++k) { if(abs(hull[i] - allpts[k]) > d.get() - EPS) continue; filter_pts.push_back(allpts[k]); } allpts = filter_pts; point pivot = hull[i]; hull = convexhull(filter_pts); for(int k = 0; k < hull.size(); ++k) if(hull[k] == pivot) i = k; reduce_mod(hull, d); } } int main() { ios_base::sync_with_stdio(false); int n; cin >> n; double dval, x, y; cin >> dval; kahan d(dval); vector pts, upper; for(int i = 0; i < n; ++i) { cin >> x >> y; if(abs(point(x, y)) > d.get() + EPS) continue; pts.push_back(point(x, y)); if(y > EPS) upper.push_back(point(x, y)); ind[dd(x, y)] = i; } if(pts.empty()) { cout << "-1\n"; return 0; } vector hull = convexhull(pts); for(int i = 0; i < hull.size(); ++i) { outer[dd(real(hull[i]), imag(hull[i]))] = i; } int cur = -1; if(upper.size() > 0) { vector upperhull = convexhull(upper); int start = 0; for(int i = 0; i < upperhull.size(); ++i) if(arg(upperhull[i]) < arg(upperhull[start])) start = i; d.add(-abs(upperhull[start])); while(upperhull.size() > 1 && !outer.count(dd(real(upperhull[start]), imag(upperhull[start])))) { move(start, upperhull, upper, d); } if(upperhull.size() == 1) { cout << ind[dd(real(upperhull[0]), imag(upperhull[0]))] + 1 << '\n'; return 0; } cur = outer[dd(real(upperhull[start]), imag(upperhull[start]))]; } if(cur == -1) { cur = 0; for(int i = 0; i < hull.size(); ++i) if(arg(hull[i]) < arg(hull[cur])) cur = i; d.add(-abs(hull[cur])); } reduce_mod(hull, d); while(hull.size() > 1) { move(cur, hull, pts, d); } cout << ind[dd(real(hull[cur]), imag(hull[cur]))] + 1 << '\n'; }