题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4520
这货我最开始写的是二分距离，查询用KD_Tree来查
然而这样的复杂度是没有保障的，于是光荣TLE
其实这货↑是写挂了，连30%的数据都没有拿到分 ←_←
然而这货的正解仍然是KD_Tree
最然感觉时间复杂度比较迷……
就是进入块中时，判断这个块是否能更新答案
#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
const int N = 100000+9;
struct Point{int x,y;}p[N];
int n,k;
struct CMP{inline bool operator () (const LL A, const LL B){return A>B;}};
priority_queue<LL,vector<LL>,CMP> que;
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}
namespace KD_Tree{
#define KDT KD_Tree
int MXx[N],MXy[N],MNx[N],MNy[N],ch[N][2],sz[N];
int root,ans_tmp,P; LL LEN;
inline bool cmpx(const Point &A, const Point &B) {return A.x < B.x;}
inline bool cmpy(const Point &A, const Point &B) {return A.y < B.y;}
inline void update(int w){
for (int i=0;i<=1;i++) if (ch[w][i]) {
MXx[w] = max(MXx[w], MXx[ch[w][i]]);
MXy[w] = max(MXy[w], MXy[ch[w][i]]);
MNx[w] = min(MNx[w], MNx[ch[w][i]]);
MNy[w] = min(MNy[w], MNy[ch[w][i]]);
sz[w] += sz[ch[w][i]];
}
}
int build(int l, int r, int ty) {
int mid = l + r >> 1; sz[mid] = 1;
if (ty) nth_element(p+l,p+mid,p+r+1,cmpx);
else nth_element(p+l,p+mid,p+r+1,cmpy);
MXx[mid] = MNx[mid] = p[mid].x;
MXy[mid] = MNy[mid] = p[mid].y;
if (l < mid) ch[mid][0] = build(l,mid-1,ty^1);
if (mid < r) ch[mid][1] = build(mid+1,r,ty^1);
update(mid); return mid;
}inline void build_Tree(){root = build(1,n,1);}
#define Pow(x) ((LL)(x)*(x))
#define DIS(p1,p2) (Pow(p[p1].x-p[p2].x)+Pow(p[p1].y-p[p2].y))
inline LL judge(int w) {
LL ret = 0;
ret += max(Pow(MXx[w]-p[P].x), Pow(MNx[w]-p[P].x));
ret += max(Pow(MXy[w]-p[P].y), Pow(MNy[w]-p[P].y));
return ret;
}
void query(int w) {
LL dw = DIS(w,P), dl = 0, dr = 0;
if (dw > que.top()) que.pop(), que.push(dw);
if (ch[w][0]) dl = judge(ch[w][0]);
if (ch[w][1]) dr = judge(ch[w][1]);
if (dl > dr) {
if (dl > que.top()) query(ch[w][0]);
if (dr > que.top()) query(ch[w][1]);
} else {
if (dr > que.top()) query(ch[w][1]);
if (dl > que.top()) query(ch[w][0]);
}
} inline void Query(const int po){P = po;query(root);}
};
int main(){
n = read(); k = read();
for (int i=1;i<=n;i++) p[i].x = read(), p[i].y = read();
for (int i=1;i<=k*2;i++) que.push(0); KDT::build_Tree();
for (int i=1;i<=n;i++) KDT::Query(i);
printf("%lld\n",que.top());
return 0;
}
貌似O(nk)的旋转卡壳也可以过？
貌似网上有一位很激动的同学说一条直线的时候没凸包？
感觉板子如果鲁棒一点的话，没有问题吧？
Good day! This is kind of off topic but I need some guidance from an established blog.
Is it very difficult to set up your own blog? I’m not very
techincal but I can figure things out pretty quick.
I’m thinking about creating my own but I’m not sure where to begin. Do you have
any points or suggestions? With thanks
I’m really impressed with your writing abilities and also with the layout in your weblog.
Is this a paid subject matter or did you modify it yourself?
Anyway keep up the nice quality writing, it is
rare to peer a nice weblog like this one nowadays..
Great blog you have got here.. It’s difficult to
find quality writing like yours nowadays. I honestly appreciate individuals like you!
Take care!!
bookmarked!!, I like your site!
Hello, Neat post. There’s a problem along with your site
in internet explorer, could check this? IE still is the marketplace chief and a big part of
folks will pass over your wonderful writing due to this problem.
This post will help the internet visitors for setting up new website or
even a weblog from start to end.
I want to to thank you for this wonderful read!!
I absolutely enjoyed every little bit of it. I have got you book marked to check out new stuff
you post…
When some one searches for his required thing,
so he/she desires to be available that in detail, therefore that thing is
maintained over here.
I always emailed this webpage post page to all my contacts, as if like to
read it after that my contacts will too.
Hmm is anyone else encountering problems with the pictures on this blog loading?
I’m trying to figure out if its a problem on my end or if it’s the blog.
Any suggestions would be greatly appreciated.
This blog was… how do you say it? Relevant!! Finally
I have found something which helped me. Thank you!
This design is wicked! You most certainly know how to keep a reader
amused. Between your wit and your videos, I was almost moved
to start my own blog (well, almost…HaHa!) Fantastic
job. I really loved what you had to say, and more than that, how you presented it.
Too cool!
Hello There. I found your blog the use of msn. This is an extremely
smartly written article. I will make sure to bookmark it and come back to learn more of your helpful info.
Thank you for the post. I will definitely return.
I enjoy the efforts you have put in this, regards for all the great articles.
Hi I am so excited I found your webpage, I really
found you by mistake, while I was looking on Digg for something else, Regardless I am here now and would just like to say thank you for a incredible post and a all round entertaining blog (I also love the theme/design), I
don’t have time to read it all at the minute but I have book-marked
it and also added your RSS feeds, so when I have time
I will be back to read much more, Please do keep up the
superb b.
Pretty nice post. I just stumbled upon your blog and wished to mention that I have truly loved browsing your weblog posts.
In any case I will be subscribing on your rss feed
and I hope you write again very soon!
Hi just wanted to give you a brief heads up and let you know a few of the pictures aren’t loading properly.
I’m not sure why but I think its a linking issue.
I’ve tried it in two different internet browsers and
both show the same outcome.
Hi! Quick question that’s totally off topic. Do you know how to make your site mobile friendly?
My blog looks weird when browsing from my iphone4. I’m trying to find a theme or plugin that might be able to resolve this problem.
If you have any suggestions, please share. With thanks!
Hey! Do you know if they make any plugins to protect against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on. Any tips?
If some one needs to be updated with most recent technologies then he must be
visit this site and be up to date every day.
Hey would you mind letting me know which hosting company you’re working with?
I’ve loaded your blog in 3 completely different web browsers
and I must say this blog loads a lot faster then most.
Can you suggest a good hosting provider at a honest price?
Many thanks, I appreciate it!
You really make it seem really easy along with your presentation however I in finding this topic to
be really something which I feel I might by no means understand.
It kind of feels too complicated and extremely vast for
me. I’m having a look ahead on your next post, I’ll try to get the
hold of it!
Great goods from you, man. I have understand your stuff previous to and you’re just extremely great.
I actually like what you’ve acquired here, really like what you’re saying and the way
in which you say it. You make it entertaining and you still
care for to keep it smart. I can not wait to read far more from you.
This is really a terrific site.
I am extremely impressed with your writing skills and also with the
layout on your blog. Is this a paid theme or did you modify it yourself?
Anyway keep up the excellent quality writing, it’s rare to see a nice blog like this one
today.
Well I sincerely liked reading it. This subject offered by you is very useful for correct planning.