【Codeforces 713B】Searching Rectangles

题目传送门: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;
}

21 thoughts to “【Codeforces 713B】Searching Rectangles”

  1. 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?

  2. 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!

  3. 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?

  4. 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

  5. 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.

  6. 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 .

  7. 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!

  8. 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

  9. 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.

  10. 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!

  11. 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!

  12. 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!

Leave a Reply to ps4 games Cancel reply

Your email address will not be published. Required fields are marked *