题目传送门:http://codeforces.com/contest/714/problem/D
CF上做的第一道交互题!
然而考场上并没能A掉QAQ
就是二分出几个关键点,然后暴力问一问
#include<bits/stdc++.h> #define LL long long using namespace std; int n,x[5],y[5],vout[10]; 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; } inline int judge(int _x1,int _y1,int _x2,int _y2) { printf("? %d %d %d %d\n",_x1,_y1,_x2,_y2); fflush(stdout); return read(); } inline bool BETTER(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){ if (!vout[1]) return true; LL s1 = (LL)(vout[3]-vout[1] + 1)*(vout[4]-vout[2] + 1) + (LL)(vout[7]-vout[5] + 1)*(vout[8]-vout[6] + 1); LL s2 = (LL)(x2 - x1 + 1) * (y2 - y1 + 1) + (LL)(x4 - x3 + 1) * (y4 - y3 + 1); return s2 < s1; } int main(){ n = read(); int l = 1, r = n, mid, ret; while (l <= r) { mid = l + r >> 1; if (judge(1,1,mid,n) >= 1) ret = mid, r = mid-1; else l = mid+1; } x[1] = ret; l = ret, r = n, ret = 0; while (l <= r) { mid = l + r >> 1; if (judge(1,1,mid,n) >= 2) ret = mid, r = mid-1; else l = mid+1; } x[3] = ret; l = 1, r = n, ret = 0; while (l <= r) { mid = l + r >> 1; if (judge(mid,1,n,n) >= 1) ret = mid, l = mid+1; else r = mid-1; } x[2] = ret; l = 1, r = x[2], ret = 0; while (l <= r) { mid = l + r >> 1; if (judge(mid,1,n,n) >= 2) ret = mid, l = mid+1; else r = mid - 1; } x[4] = ret; l = 1, r = n, ret = 0; while (l <= r) { mid = l + r >> 1; if (judge(1,1,n,mid) >= 1) ret = mid, r = mid-1; else l = mid+1; } y[1] = ret; l = y[1], r = n, ret = 0; while (l <= r) { mid = l + r >> 1; if (judge(1,1,n,mid) >= 2) ret = mid, r = mid-1; else l = mid+1; } y[3] = ret; l = 1, r = n, ret = 0; while (l <= r) { mid = l + r >> 1; if (judge(1,mid,n,n) >= 1) ret = mid, l = mid+1; else r = mid-1; } y[2] = ret; l = 1, r = y[2], ret = 0; while (l <= r) { mid = l + r >> 1; if (judge(1,mid,n,n) >= 2) ret = mid, l = mid+1; else r = mid-1; } y[4] = ret; sort(x+1,x+5); sort(y+1,y+5); for (int s=1;s<=4;s++) for (int i=s+1;i<=4;i++) for (int j=1;j<=4;j++) for (int k=j+1;k<=4;k++) if (judge(x[s],y[j],x[i],y[k]) == 1) { int x1,x2,y1,y2; for (int u=1;u<=4;u++) if (u != i && u != s) {x1=u; break;} for (int u=x1+1;u<=4;u++) if (u != i && u != s) {x2=u; break;} for (int u=1;u<=4;u++) if (u != j && u != k) {y1 = u; break;} for (int u=y1+1;u<=4;u++) if (u != j && u != k) {y2=u;break;} if (x[x1] > x[i] || x[x2] < x[s] || y[y1] > y[k] || y[y2] < y[j]) if (judge(x[x1],y[y1],x[x2],y[y2]) == 1 && BETTER(x[s],y[j],x[i],y[k],x[x1],y[y1],x[x2],y[y2])) vout[1]=x[s],vout[2]=y[j],vout[3]=x[i],vout[4]=y[k],vout[5]=x[x1],vout[6]=y[y1],vout[7]=x[x2],vout[8]=y[y2]; } putchar('!'); for (int i=1;i<=8;i++) printf(" %d",vout[i]); return 0; }
hello!,I really like your writing very so much!
share we keep in touch more about your article on AOL? I need a specialist on this house to resolve my problem.
May be that’s you! Taking a look forward to look you.
I am curious to find out what blog platform you are using?
I’m having some small security issues with my latest site and I would like
to find something more secure. Do you have any suggestions?
I absolutely love your website.. Very nice colors & theme.
Did you create this site yourself? Please reply back as I’m trying to create my very own blog and would love to find out
where you got this from or just what the theme is called.
Cheers!
I was curious if you ever thought of changing the layout of your
website? Its very well written; I love what youve got to say.
But maybe you could a little more in the way of content so people could connect with it
better. Youve got an awful lot of text for only having 1 or 2
pictures. Maybe you could space it out better?
It’s remarkable designed for me to have a web page, which is useful for my know-how.
thanks admin
Excellent beat ! I would like to apprentice while you amend your web site,
how can i subscribe for a weblog site? The account aided me
a appropriate deal. I had been tiny bit familiar
of this your broadcast offered brilliant transparent concept
Simply wish to say your article is as amazing.
The clearness in your post is simply great and i could assume
you’re an expert on this subject. Well with your permission let me to grab your feed to keep updated with forthcoming post.
Thanks a million and please carry on the gratifying work.
Hello my friend! I want to say that this post is awesome, great written and
include approximately all important infos. I’d like to peer
more posts like this .
Have you ever thought about including a little bit more
than just your articles? I mean, what you say is fundamental and all.
However think about if you added some great images or videos to give your posts more,
“pop”! Your content is excellent but with images and clips, this blog
could undeniably be one of the best in its niche.
Awesome blog!
Hi to every body, it’s my first go to see of this web site; this weblog includes
awesome and truly excellent stuff designed for readers.
I think this is among the most significant information for me.
And i am glad reading your article. But should remark on few general things, The web site style is wonderful, the articles is really excellent : D.
Good job, cheers
Hello I am so happy I found your blog, I really found you by accident, while I was looking on Yahoo for something else, Nonetheless I am here now and would just like to say kudos for a tremendous post and a all round enjoyable blog (I also love the theme/design), I don’t have time to read it all at the moment but I have book-marked it and also included your RSS feeds, so when I have time I will be back to read more, Please do keep up the superb job.
Very good blog post. I definitely love this site.
Continue the good work!
I think this is one of the most significant information for me.
And i am glad reading your article. But wanna remark on some general things, The
web site style is ideal, the articles is really nice : D.
Good job, cheers
I have read so many articles regarding the blogger lovers except this paragraph is
truly a pleasant article, keep it up.
Greetings from California! I’m bored to tears at work so
I decided to browse your website on my iphone during lunch break.
I love the info you present here and can’t wait to
take a look when I get home. I’m shocked at how quick your blog
loaded on my phone .. I’m not even using WIFI, just 3G .. Anyhow, very good blog!
Greetings! I know this is somewhat off topic but I was wondering if you knew where I could find a captcha
plugin for my comment form? I’m using the same blog platform as
yours and I’m having problems finding one? Thanks a lot!
First of all I would like to say awesome blog!
I had a quick question which I’d like to ask if you do not mind.
I was curious to know how you center yourself and clear your thoughts before
writing. I’ve had a tough time clearing my thoughts in getting my thoughts out.
I do take pleasure in writing however it just seems like the first 10 to 15 minutes are usually wasted simply just trying to figure out how to begin. Any ideas or tips?
Thanks!
Hi there are using WordPress for your blog platform?
I’m new to the blog world but I’m trying to
get started and create my own. Do you need any coding
expertise to make your own blog? Any help would be greatly appreciated!
It’s great that you are getting ideas from this post as well as from our dialogue
made at this time.
You made some respectable factors there. I appeared on the web for the issue and located most people will go along with together with your website.