#include using namespace std; typedef long long ll; const double EPS = 1e-9; struct kahan { double s, c; kahan(double _s) : s(_s), c(0.0) { } void add(double d) { double y = d - c; double t = s + y; c = (t - s) - y; s = t; } double get() { return s; } }; // Implementation of decremental convex hull is from dacin21, source is // "Applications of a semi-dynamic convex hull algorithm" // Authors are John Hershberger and Subhash Suri struct Point { Point& operator+=(Point const&o) { x+=o.x; y+=o.y; return *this; } Point& operator-=(Point const&o) { x-=o.x; y-=o.y; return *this; } Point operator-() const { return Point{-x, -y}; } friend Point operator+(Point a, Point const&b){ a+=b; return a; } friend Point operator-(Point a, Point const&b){ a-=b; return a; } friend ll dot(Point const&a, Point const&b){ return a.x*b.x + a.y*b.y; } friend ll cross(Point const&a, Point const&b){ return a.x*b.y - a.y*b.x; } friend bool operator<(Point const&a, Point const&b){ return tie(a.x, a.y) < tie(b.x, b.y); } friend bool operator==(Point const&a, Point const&b){ return a.x == b.x && a.y == b.y; } double distance(Point const &o) { double dx = x - o.x, dy = y - o.y; return sqrt(dx * dx + dy * dy); } ll x=0, y=0; }; int ccw(Point const&a, Point const&b){ ll x = cross(a, b); return (x>0)-(x<0); } int ccw(Point const&a, Point const&b, Point const&c){ return ccw(b-a, c-a); } // Decremental convex hull in O(n log n) // From "Applications of a semi-dynamic convex hull algorithm" by J. Hershberger and S. Suri struct UpperHull { struct Link { Point p; Link *prev = nullptr, *next = nullptr; int id; }; struct Node { Link *chain, *chain_back; Link *tangent; }; template pair find_bridge(Link*l, Link*r, S next, T convex) { while(next(l) || next(r)){ if(!next(r) || (next(l) && convex(Point{0, 0}, next(l)->p - l->p, next(r)->p - r->p))){ if(convex(l->p, next(l)->p, r->p)){ l = next(l); } else { break; } } else { if(!convex(l->p, r->p, next(r)->p)){ r = next(r); } else { break; } } } return {l, r}; } template void fix_chain(int u, Link *l, Link *r) { if(rev){ // l and r to the right of actual bridge tie(r, l) = find_bridge(r, l, [](Link*x){ return x->prev; }, [](Point const&a, Point const&b, Point const&c){ return ccw(a, b, c) >= 0; }); } else { // l and r to the left of actual bridge tie(l, r) = find_bridge(l, r, [](Link*x){ return x->next; }, [](Point const&a, Point const&b, Point const&c){ return ccw(a, b, c) <= 0; }); } tree[u].tangent = l; tree[u].chain = tree[2*u].chain; tree[u].chain_back = tree[2*u+1].chain_back; tree[2*u].chain = l->next; tree[2*u+1].chain_back = r->prev; if(l->next){ l->next->prev = nullptr; } else { tree[2*u].chain_back = nullptr; } if(r->prev){ r->prev->next = nullptr; } else { tree[2*u+1].chain = nullptr; } l->next = r; r->prev = l; } void build(int u, int a, int b){ if(b-a == 1){ tree[u].chain = tree[u].chain_back = &lists[a]; tree[u].tangent = nullptr; return; } const int m = a + (b-a)/2; build(2*u, a, m); build(2*u+1, m, b); auto l = tree[2*u].chain, r = tree[2*u+1].chain; fix_chain(u, l, r); } void rob(int u, int v){ tree[u].chain = tree[v].chain; tree[v].chain = nullptr; tree[u].chain_back = tree[v].chain_back; tree[v].chain_back = nullptr; } void remove(int u, int a, int b, int const&i){ if(i < a || i >= b) return; // we should never hit a leaf assert(b-a > 1); const int m = a + (b-a)/2; // one child -> that child contains i if(!tree[u].tangent){ int v = inext; l->next = tree[2*u].chain; if(tree[2*u].chain){ tree[2*u].chain->prev = l; } else { tree[2*u].chain_back = l; } tree[2*u].chain = tree[u].chain; r->prev = tree[2*u+1].chain_back; if(tree[2*u+1].chain_back){ tree[2*u+1].chain_back->next = r; } else { tree[2*u+1].chain = r; } tree[2*u+1].chain_back = tree[u].chain_back; // delete i const int v = iid == i){ tree[v].chain = tree[v].chain_back = nullptr; rob(u, v^1); tree[u].tangent = nullptr; return; } if(i < m){ if(l->id == i){ l = l->next; } remove(2*u, a, m, i); if(!l){ l = tree[2*u].chain_back; } fix_chain(u, l, r); } else { if(r->id == i){ r = r->prev; } remove(2*u+1, m, b, i); if(!r){ r = tree[2*u+1].chain; } fix_chain(u, l, r); } } void remove(int i){ left--; // i is the only point if(tree[1].chain == tree[1].chain_back){ tree[1].chain = tree[1].chain_back = nullptr; return; } remove(1, 0, n, i); } UpperHull() : n(0), tree(), lists() { } UpperHull(vector const&v) : n(v.size()), tree(4*n), lists(n){ assert(is_sorted(v.begin(), v.end())); for(int i=0; i get_hull(){ vector ret; for(Link* u = tree[1].chain; u; u=u->next){ ret.push_back(u->id); } return ret; } vector get_hull_points(){ vector ret; for(Link* u = tree[1].chain; u; u=u->next){ ret.push_back(u->p); } return ret; } int n, left; vector tree; vector lists; }; struct FullHull { int n, pos; bool on_upper; UpperHull upper, lower; FullHull(vector ps) : n(ps.size()) { sort(ps.begin(), ps.end()); upper = UpperHull(ps); reverse(ps.begin(), ps.end()); for(auto &p : ps) p = -p; lower = UpperHull(ps); for(auto &p : ps) p = -p; reverse(ps.begin(), ps.end()); } void set_start(Point start) { pos = -1; for(int i : upper.get_hull()) { if(upper.lists[i].p == start) { pos = i; on_upper = true; } } for(int i : lower.get_hull()) { if(lower.lists[i].p == -start) { pos = n - i - 1; on_upper = false; } } assert(pos != -1); } void remove(int i) { upper.remove(i); lower.remove(n - i - 1); } set get_hull() { set res; for(int i : upper.get_hull()) res.insert(i); for(int i : lower.get_hull()) res.insert(n - i - 1); return res; } int half_size() { return upper.left; } vector move(kahan &rope) { vector del; while(true) { if(half_size() < 3) return small_move(rope); int nxt = -1; if(on_upper) { // if(!upper.lists[pos].prev) { if(n - lower.tree[1].chain_back->id - 1 == pos) { on_upper = !on_upper; continue; } else { nxt = upper.lists[pos].prev->id; } } else { // if(!lower.lists[n - pos - 1].prev) { if(upper.tree[1].chain_back->id == pos) { on_upper = !on_upper; continue; } else { nxt = n - lower.lists[n - pos - 1].prev->id - 1; } } double dist = upper.lists[pos].p.distance(upper.lists[nxt].p); if(dist > rope.get() + EPS) { upper.remove(nxt); lower.remove(n - nxt - 1); del.push_back(nxt); continue; } rope.add(-dist); pos = nxt; break; } return del; } vector small_move(kahan &rope) { vector del; int oth = -1; for(int i : upper.get_hull()) if(i != pos) oth = i; double dist = upper.lists[pos].p.distance(upper.lists[oth].p); rope.s = fmod(rope.s, 2 * dist); if(dist < rope.get()) swap(pos, oth), rope.add(-dist); del.push_back(oth); upper.remove(oth); lower.remove(n - oth - 1); return del; } }; double myarg(Point p) { double th = atan2(p.y, p.x); return th < 0 ? th + 2 * M_PI : th; } int main() { ios_base::sync_with_stdio(false); int n; ll x, y, dwhole; cin >> n >> dwhole; kahan d(dwhole); map id; vector ps, half; int pos = 0; for(int i = 0; i < n; ++i) { cin >> x >> y; if(x * x + y * y > dwhole * dwhole) continue; id[{x, y}] = i + 1; ps.push_back({x, y}); if(myarg(ps.back()) < myarg(ps[pos])) pos = ps.size() - 1; } n = ps.size(); if(ps.empty()) { cout << "-1\n"; return 0; } if(ps.size() == 1) { d.add(-ps[0].distance({0, 0})); cout << id[ps[0]] << '\n'; return 0; } Point cur = ps[pos]; d.add(-cur.distance({0, 0})); FullHull halfplane(ps), allpts(ps); for(int i = 0; i < n; ++i) if(halfplane.upper.lists[i].p.y <= 0) halfplane.remove(i); if(halfplane.half_size() > 0) { halfplane.set_start(cur); set hullpts = allpts.get_hull(); // Iterate along internal points while(!hullpts.count(halfplane.pos)) { vector del = halfplane.move(d); for(int x : del) allpts.remove(x); } cur = halfplane.upper.lists[halfplane.pos].p; } allpts.set_start(cur); while(allpts.half_size() > 1) { allpts.move(d); } cout << id[allpts.upper.lists[allpts.pos].p] << '\n'; }