#include using namespace std; // stuff from kactl #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define endl "\n" using ll = long long; using pii = pair; using vi = vector; template int sgn(T x) { return (x > 0) - (x < 0); } template struct Point { typedef Point P; T x, y; explicit Point(T x=0, T y=0) : x(x), y(y) {} bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); } bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } P operator+(P p) const { return P(x+p.x, y+p.y); } P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(T d) const { return P(x*d, y*d); } P operator/(T d) const { return P(x/d, y/d); } T dot(P p) const { return x*p.x + y*p.y; } T cross(P p) const { return x*p.y - y*p.x; } T cross(P a, P b) const { return (a-*this).cross(b-*this); } T dist2() const { return x*x + y*y; } double dist() const { return sqrt((double)dist2()); } // angle to x-axis in interval [0, 2pi] double angle() const { double r = atan2(y, x); return r < 0.0? r + 2 * M_PI : r; } P unit() const { return *this/dist(); } // makes dist()=1 P perp() const { return P(-y, x); } // rotates +90 degrees P normal() const { return perp().unit(); } // returns point rotated 'a' radians ccw around the origin P rotate(double a) const { return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); } friend ostream& operator<<(ostream& os, P p) { return os << "(" << p.x << "," << p.y << ")"; } }; typedef Point P; vector

convexHull(vector

pts) { if (sz(pts) <= 1) return pts; sort(all(pts)); vector

h(sz(pts)+1); int s = 0, t = 0; for (int it = 2; it--; s = --t, reverse(all(pts))) for (P p : pts) { while (t >= s + 2 && h[t-2].cross(h[t-1], p) <= 0) t--; h[t++] = p; } return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])}; } /* Straightforward port of oskar.py to C++ */ const double EPS = 1e-7; struct Node { Node *prev, *next, *prev_hull, *next_hull; P p; Node() : prev_hull(nullptr), next_hull(nullptr) {} bool on_hull() { return prev_hull != nullptr; } }; const int MAXN = 1e5; int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int N; ll Di; cin >> N >> Di; vector

OP(N); for(auto& p: OP) cin >> p.x >> p.y; vector

Ps; for(auto& p: OP) if (p.dist2() <= Di * Di) Ps.push_back(p); P C{0, 0}; double D = Di; auto ans = [&](){ if (C == P{0, 0}) cout << -1 << endl; else cout << (find(all(OP), C) - OP.begin())+1 << endl; exit(0); }; if (sz(Ps) == 0) ans(); auto move = [&](const P& to) { D -= (to - C).dist(); C = to; }; vector

uhp; for (auto& p: Ps) if (p.y > 0) uhp.push_back(p); auto upper_hull = convexHull(uhp); auto full_hull = convexHull(Ps); set

full_hull_pts(all(full_hull)); if (sz(upper_hull) > 0 && sz(uhp) != sz(Ps)) { int hit = -1; rep(i, 0, sz(upper_hull)) if (hit == -1 || upper_hull[i].angle() < upper_hull[hit].angle()) hit = i; move(upper_hull[hit]); while (!full_hull_pts.count(C)) { hit = (hit + 1) % sz(upper_hull); const P& p = upper_hull[hit]; if ((p - C).dist2() > D * D + EPS) break; move(p); } } Ps.erase(remove_if(all(Ps), [&](const P& p) { return (p - C).dist2() > D * D + EPS; }), Ps.end()); sort(all(Ps)); assert(sz(Ps)); if (sz(Ps) == 1) { assert(C == Ps[0]); ans(); } { vector

cp(Ps.rbegin()+1, Ps.rend()-1); Ps.insert(Ps.end(), all(cp)); } vector nodes(sz(Ps)); rep(i, 0, sz(Ps)) { Node* n = &nodes[i]; n->p = Ps[i]; Node* pr = i == 0? &nodes[sz(nodes)-1] : &nodes[i-1]; pr->next = n; n->prev = pr; } auto get_hull_nodes = [&](Node* n) { Node* c = n; vector ns; while(1) { ns.push_back(c); c = c->next_hull; if (c == n) return ns; } }; Node* cur_node = &nodes[0]; int nodes_on_hull = 1; auto remove_from_hull = [&](Node* n) { assert(n->prev_hull && n->next_hull); nodes_on_hull--; n->prev_hull->next_hull = n->next_hull; n->next_hull->prev_hull = n->prev_hull; Node* tmp = n->prev_hull; n->prev_hull = n->next_hull = nullptr; assert(tmp && tmp->on_hull()); return tmp; }; auto add_to_hull = [&](Node* prev, Node* n) { assert(!n->on_hull() && prev->next_hull); nodes_on_hull++; n->prev_hull = prev; n->next_hull = prev->next_hull; prev->next_hull = n->next_hull->prev_hull = n; }; cur_node->prev_hull = cur_node->next_hull = cur_node; cur_node = cur_node->next; while(1) { Node* prev = cur_node->prev; assert(prev->prev_hull && prev->next_hull && prev->on_hull()); while (nodes_on_hull >= 2 && prev->prev_hull->p.cross(prev->p, cur_node->p) < 0) { prev = remove_from_hull(prev); assert(prev->prev_hull); } if (cur_node->on_hull()) break; add_to_hull(prev, cur_node); cur_node = cur_node->next; } assert(nodes_on_hull >= 2 && nodes[0].on_hull()); auto initial_nodes_on_hull = get_hull_nodes(cur_node); if (C == P{0, 0}) { cur_node = *min_element(all(initial_nodes_on_hull), [](Node* a, Node* b) { return a->p.angle() < b->p.angle(); }); move(cur_node->p); } else { for (Node* n : initial_nodes_on_hull) { if (n->p == C) { cur_node = n; goto found; } } assert(0); found:; } auto remove = [&](Node* n) { if (n->on_hull()) remove_from_hull(n); n->prev->next = n->next; n->next->prev = n->prev; return n->next; }; double hull_size = 0.; rep(_, 0, nodes_on_hull) { Node* nxt = cur_node->next_hull; hull_size += (nxt->p - cur_node->p).dist(); cur_node = nxt; } D = fmod(D, hull_size); { set

initial_points_on_hull; for (Node* n : initial_nodes_on_hull) initial_points_on_hull.insert(n->p); for (Node& n : nodes) if (initial_points_on_hull.count(n.p) && !n.on_hull()) remove(&n); } Node* hull_start = cur_node; auto rebuild_hull = [&](Node* cur_node) { assert(cur_node->on_hull()); int removed = 0; hull_size = 0.; cur_node = cur_node->next; while(1) { if ((C - cur_node->p).dist() >= D + EPS) { removed++; cur_node = remove(cur_node); continue; } Node* prev = cur_node->prev; assert(prev->on_hull()); while (nodes_on_hull >= 2 && prev->prev_hull->p.cross(prev->p, cur_node->p) < 0) prev = remove_from_hull(prev); if (cur_node->on_hull()) { assert(cur_node->prev_hull == prev); if (cur_node != prev && cur_node->prev == prev && cur_node->p == prev->p) { assert(prev != hull_start); removed++; remove(prev); } break; } if (cur_node->p == prev->p) { assert(cur_node->prev == prev && cur_node != hull_start); removed++; cur_node = remove(cur_node); } else { add_to_hull(prev, cur_node); cur_node = cur_node->next; } } assert(removed); }; hull_size = 0.; while (nodes_on_hull > 1) { assert(cur_node->on_hull() && cur_node->p == C); Node* nxt = cur_node->next_hull; hull_size += (C - nxt->p).dist(); if (nxt == hull_start) D = fmod(D, hull_size); if ((C - nxt->p).dist() < D + EPS) { move(nxt->p); cur_node = nxt; } else { hull_start = cur_node; rebuild_hull(cur_node); } } assert(cur_node->on_hull() && cur_node->p == C); ans(); }