首页 > 代码库 > 【bzoj1941】 Sdoi2010—Hide and Seek
【bzoj1941】 Sdoi2010—Hide and Seek
http://www.lydsy.com/JudgeOnline/problem.php?id=1941 (题目链接)
题意
给出n个二维平面上的点,求一点使到最远点的距离-最近点的距离最小。
Solution
KDtree板子,早就听jump说KDtree都是板子题→_→
枚举点,求其最远点距离和最近点距离,更新答案。最远邻近域搜索跟最近差不多,就是把估价函数改一下。
细节
码农题注意细节
代码
// bzoj1941#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 1<<30#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=1000010,maxm=2;int n,K,ans1,ans2,rt;struct KDtree { int v[maxm],mn[maxm],mx[maxm],l,r; friend bool operator < (const KDtree a,const KDtree b) { return a.v[K]<b.v[K]; }}tr[maxn],S;int dis(KDtree a,KDtree b) { int res=0; for (int i=0;i<=1;i++) res+=abs(a.v[i]-b.v[i]); return res;}int eva1(int k) { if (!k) return inf; int res=0; for (int i=0;i<=1;i++) res+=max(0,S.v[i]-tr[k].mx[i])+max(0,tr[k].mn[i]-S.v[i]); return res;}int eva2(int k) { if (!k) return 0; int res=0; for (int i=0;i<=1;i++) res+=max(tr[k].mx[i]-S.v[i],S.v[i]-tr[k].mn[i]); return res;} void update(int k) { if (tr[k].l) for (int i=0;i<=1;i++) { tr[k].mx[i]=max(tr[k].mx[i],tr[tr[k].l].mx[i]); tr[k].mn[i]=min(tr[k].mn[i],tr[tr[k].l].mn[i]); } if (tr[k].r) for (int i=0;i<=1;i++) { tr[k].mx[i]=max(tr[k].mx[i],tr[tr[k].r].mx[i]); tr[k].mn[i]=min(tr[k].mn[i],tr[tr[k].r].mn[i]); }}int build(int l,int r,int p) { K=p; int mid=(l+r)>>1; nth_element(tr+l,tr+mid,tr+r+1); for (int i=0;i<=1;i++) tr[mid].mn[i]=tr[mid].mx[i]=tr[mid].v[i]; if (l<mid) tr[mid].l=build(l,mid-1,p^1); if (mid<r) tr[mid].r=build(mid+1,r,p^1); update(mid); return mid;}void query1(int k) { if (S.v[0]!=tr[k].v[0] || S.v[1]!=tr[k].v[1]) ans1=min(ans1,dis(S,tr[k])); int dl=eva1(tr[k].l),dr=eva1(tr[k].r); if (dl<dr) { if (dl<ans1) query1(tr[k].l); if (dr<ans1) query1(tr[k].r); } else { if (dr<ans1) query1(tr[k].r); if (dl<ans1) query1(tr[k].l); }}void query2(int k) { ans2=max(ans2,dis(S,tr[k])); int dl=eva2(tr[k].l),dr=eva2(tr[k].r); if (dl>dr) { if (dl>ans2) query2(tr[k].l); if (dr>ans2) query2(tr[k].r); } else { if (dr>ans2) query2(tr[k].r); if (dl>ans2) query2(tr[k].l); }}int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d%d",&tr[i].v[0],&tr[i].v[1]); rt=build(1,n,0); int ans=inf; for (int i=1;i<=n;i++) { S=tr[i]; ans1=inf;query1(rt); //最小 ans2=0;query2(rt); //最大 ans=min(ans,ans2-ans1); } printf("%d",ans); return 0;}
【bzoj1941】 Sdoi2010—Hide and Seek
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。