#include using namespace std; const int N = 5005; int x[N], y[N]; int xx[N], yy[N]; int px[N], py[N]; class Segment{ public: int xl, xr, xmid; Segment *lptr, *midptr, *rptr; vector data; Segment() {lptr=midptr=rptr=nullptr;} }; Segment* build(vector data) { Segment* ret = new Segment(); sort(data.begin(), data.end(), [&](int i, int j) { if(xx[i]!=xx[j]) return xx[i] < xx[j]; if(yy[i]!=yy[j]) return yy[i] < yy[j]; return idata = data; // copy ret->xl = xx[data[0]]; ret->xr = xx[data.back()]; ret->xmid = xx[data[len/2]]; sort(ret->data.begin(), ret->data.end(), [&](int i, int j) { if (yy[i]!=yy[j]) return yy[i] < yy[j]; if (xx[i]!=xx[j]) return xx[i] < xx[j]; return ixl == ret->xr) return ret; int mid=len/2; while(mid>0 && xx[data[mid-1]]==xx[data[mid]]) --mid; if(mid>0) { ret->lptr = build(vector(data.begin(), data.begin() + mid)); } int midl = mid; mid=len/2; while(mid+1rptr = build(vector(data.begin() + mid + 1, data.end())); } int midr = mid; ret->midptr = build(vector(data.begin() + midl, data.begin() + midr + 1)); return ret; } int nt, ns, rmax; const int OFFSET=524288; const long long MASK=(1LL<<20)-1; unordered_set dict; unordered_set alltrees; long long enc(int vx, int vy) { return (vx+OFFSET)*(1LL<<20)+(vy+OFFSET); } void dec(int &vx, int &vy, long long val) { vx=(val>>20) - OFFSET; vy=(val&MASK) - OFFSET; } int mysearch(const vector& data, int yl) { int l=0,r=(int)data.size()-1, ans=(int)data.size(); while(l<=r) { int m=(l+r)/2; if(yy[data[m]] < yl) { l=m+1; } else { ans=m; r=m-1; } } return ans; } const int infcnt=100000; int xl, xr, yl, yr, cx, cy; int ask(Segment *node) { int ret=0; if (node->xl > xr || node->xr < xl) return 0; if (node->xl >= xl && node->xr <= xr) { int idx = mysearch(node->data, yl); while(idxdata.size() && yy[node->data[idx]] <= yr) { int c = node->data[idx]; if(dict.find(enc(x[c]-cx, y[c]-cy)) == dict.end()) { return infcnt; } ++ret; ++idx; } return ret; } if(node->lptr) ret += ask(node->lptr); if(node->midptr) ret += ask(node->midptr); if(node->rptr) ret += ask(node->rptr); int retv= min(ret, infcnt); return retv; } bool query(Segment *root, int _cx, int _cy) { cx=_cx;cy=_cy; xl=cx-cy-rmax; xr=cx-cy+rmax; yl=cx+cy-rmax; yr=cx+cy+rmax; int ret = ask(root); return (ret == ns) ; } int bestcnt=0, bestx, besty; void solve(Segment* root) { dict.clear(); for(int i=0;i cnt; for(int i=0;i all; for(int i=0;i1) puts("Ambiguous"); else printf("%d %d\n", bestx, besty); return 0; }