Codeforces Round #371 (Div. 2) D. Searching Rectangles 平面矩形二分法、交互题

Source

Codeforces Round #371 (Div. 2)

My Solution

平面矩形二分法、交互题

先切一条与x轴平行的线把 2个矩形分隔开， 然后变成从 框框类确定一个矩形的坐标这样的子问题，

对于那条与x轴平行且把2个矩形分隔开的线可以通过 二分法 logn的复杂度找到，

如果没有与x轴平行且把2个矩形分隔开的线， 则 比有一条 与 y轴平行且把2个矩形分隔开的线， 也是 logn的复杂度可以找到

然后确定单个矩形所在的大致区域以后 可以 分成4次 用 4个二分 分别二分x = x1, x = x2, y = y1, y = y2 这4条线， 确定一条线以后就确定了一个相应的坐标，从而求出 x1, x2, y1, y2

 ---------------------------------

      |                       |

     |                        |

     |                        |

---------------------------------

总共要确定2个矩形， 共 8 个点， 所以 复杂度 O(8logn);

此外在代码实现上，还有一些小注意点， 已经用注释的方式标在了源码里 ☺☺。 题目挺好的， 想到思路不难，但正确的代码实现挺辛苦了， 写了许久，也WA好几发，Debug了比较长的时间  ⊙﹏⊙‖∣。

还有，做交互题的时候， 不要(不能) 用 cin.tie(0); 否则会出问题的。

对于 "cin.tie(0);" 的功能，

在默认的情况下cin绑定的是cout，每次执行 << 操作符的时候都要调用flush，这样会增加IO负担。可以通过tie(0)（0表示NULL）来解除cin与cout的绑定，进一步加快执行效率。

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 8;

void  confirm_a_rectangle(LL &x1, LL &y1, LL &x2, LL &y2)
{
    LL op, tptr, mid;


    //x1
    mid = x1;
    tptr = x2;
    if(x1 + 1 < tptr) cout << "? " << x1 + 1 << " " << y1 + 1 << " " << x2 << " " << y2 << "n"; fflush(stdout);
    while(x1 + 1 < tptr){ cin >> op;
        if(op == 1){
            x1 = mid;
            mid = (x1 + tptr) / 2;
            if(!(x1 + 1 < tptr)) break; // 不多余的输出下面这句
            cout << "? " << mid + 1 << " " << y1 + 1 << " " << x2 << " " << y2 << "n"; fflush(stdout);
        }
        else if(op == 0){
            tptr = mid;
            mid = (x1 + tptr) / 2;
            if(!(x1 + 1 < tptr)) break; // 不多余的输出下面这句
            cout << "? " << mid + 1 << " " << y1 + 1 << " " << x2 << " " << y2 << "n"; fflush(stdout);

        }
    }
    //cout << "x1 " << x1 << endl;
    //x2

    mid = x2;
    tptr = x1;
    if(tptr + 1 < x2) cout << "? " << x1 + 1 << " " << y1 + 1 << " " << x2 << " " << y2 << "n"; fflush(stdout);
    while(tptr + 1 < x2){ cin >> op;
        if(op == 1){
            x2 = mid;
            mid = (x2 + tptr) / 2;
            //
            if(mid == 0) break;
            if(!(tptr + 1 < x2)) break; // 不多余的输出下面这句
            cout << "? " << x1 + 1 << " " << y1 + 1 << " " << mid << " " << y2 << "n"; fflush(stdout);
        }
        else if(op == 0){
            tptr = mid;
            mid = (x2 + tptr) / 2;
            //
            if(mid == 0) break;
            if(!(tptr + 1 < x2)) break; // 不多余的输出下面这句
            cout << "? " << x1 + 1 << " " << y1 + 1 << " " << mid << " " << y2 << "n"; fflush(stdout);

        }
    }
    //cout << "x2 " << x2 << endl;
    //y1


    mid = y1;
    tptr = y2;
    if(y1 + 1 < tptr) cout << "? " << x1 + 1 << " " << y1 + 1 << " " << x2 << " " << y2 << "n"; fflush(stdout);
    while(y1 + 1 < tptr){ cin >> op;
        if(op == 1){
            y1 = mid;
            mid = (y1 + tptr) / 2;
            if(!(y1 + 1 < tptr)) break; // 不多余的输出下面这句
            cout << "? " << x1 + 1 << " " << mid + 1 << " " << x2 << " " << y2 << "n"; fflush(stdout);
        }
        else if(op == 0){
            tptr = mid;
            mid = (y1 + tptr) / 2;
            if(!(y1 + 1 < tptr)) break; // 不多余的输出下面这句
            cout << "? " << x1 + 1 << " " << mid + 1 << " " << x2 << " " << y2 << "n"; fflush(stdout);

        }
    }
   //cout << "y1 " << y1 << endl;
    //y2


    mid = y2;
    tptr = y1;
    if(tptr + 1 < y2) cout << "? " << x1 + 1 << " " << y1 + 1 << " " << x2 << " " << y2 << "n"; fflush(stdout);
    //前面WA是因为这里， 直接输出了， 但并没有进入while
    while(tptr + 1 < y2){ cin >> op;
        if(op == 1){
            y2 = mid;
            mid = (y2 + tptr) / 2;
            //
            if(mid == 0) break;
            if(!(tptr + 1 < y2)) break;  不多余的输出下面这句
            cout << "? " << x1 + 1 << " " << y1 + 1 << " " << x2 << " " << mid << "n"; fflush(stdout);
        }
        else if(op == 0){
            tptr = mid;
            mid = (y2 + tptr) / 2;
            //
            if(mid == 0) break;
            if(!(tptr + 1 < y2)) break;  不多余的输出下面这句
            cout << "? " << x1 + 1 << " " << y1 + 1 << " " << x2 << " " << mid << "n"; fflush(stdout);

        }
    }
    //cout << "y2 " << y2 << endl; } int main() { #ifdef LOCAL //freopen("d.txt", "r", stdin); //freopen("o.txt", "w", stdout); int T = 1; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); //cin.tie(0);j交互题 不能用 cin.tie(0); 来加速IO LL n, op, x1, y1, x2, y2, mid, ansx1 = -1, ansy1 = -1, ansx2 = -1, ansy2 = -1, ansx3 = -1, ansy3 = -1, ansx4 = -1, ansy4 = -1; cin >> n;
    x1 = y1 = 0, x2 = y2 = n;


    //while(true){
        //go down or go down
        cout << "? " << 1 << " " << 1 << " " << n << " " << n << "n"; fflush(stdout);
        mid = n;
        while(y1 + 1 < y2){ cin >> op;
            if(op == 2){
                y2 = mid;
                mid = (y1 + y2) / 2;
                //
                if(mid == 0) break;
                if(!(y1 + 1 < y2)) break;
                cout << "? " << 1 << " " << 1 << " " << n << " " << mid << "n"; fflush(stdout);
            }
            else if(op == 1){
                cout << "? " << 1 << " " << mid + 1 << " " << n << " " << n << "n"; fflush(stdout); cin >> op;
                if(op == 1){
                    //!!!!!! 已划分出2个矩形
                    ansx1 = 0, ansy1 = 0, ansx2 = n, ansy2 = mid;
                    confirm_a_rectangle(ansx1, ansy1, ansx2, ansy2);

                    ansx3 = 0, ansy3 = mid, ansx4 = n, ansy4 = n;
                    confirm_a_rectangle(ansx3, ansy3, ansx4, ansy4);

                    cout << "! " << ansx1 + 1 << " " << ansy1 + 1 << " " << ansx2 << " " << ansy2 <<" "
                    << ansx3 + 1 << " " << ansy3 + 1 << " " << ansx4 << " " << ansy4 << "n"; fflush(stdout);
                    exit(0);
                }
                else if(op == 0){
                    y2 = mid;
                    mid = (y1 + y2) / 2;
                    //
                    if(mid == 0) break;
                    if(!(y1 + 1 < y2)) break;
                    cout << "? " << 1 << " " << 1 << " " << n << " " << mid << "n"; fflush(stdout);
                }
            }
            else if(op == 0){
                y1 = mid;
                mid = (y1 + y2) / 2;
                //
                if(mid == 0) break;
                if(!(y1 + 1 < y2)) break;
                cout << "? " << 1 << " " << 1 << " " << n << " " << mid << "n"; fflush(stdout); } } //go rights or left //cin >> op;
        cout << "? " << 1 << " " << 1 << " " << n << " " << n << "n"; fflush(stdout);
        mid = n;
        while(x1 + 1 < x2){ cin >> op;
            if(op == 2){
                x2 = mid;
                mid = (x1 + x2) / 2;
                cout << "? " << 1 << " " << 1 << " " << mid << " " << n << "n"; fflush(stdout);
            }
            else if(op == 1){
                cout << "? " << mid + 1 << " " << 1 << " " << n << " " << n << "n"; fflush(stdout); cin >> op;
                if(op == 1){
                    //!!!!!! 已划分出2个矩形
                    ansx1 = 0, ansy1 = 0, ansx2 = mid, ansy2 = n;
                    confirm_a_rectangle(ansx1, ansy1, ansx2, ansy2);

                    ansx3 = mid, ansy3 = 0, ansx4 = n, ansy4 = n;
                    confirm_a_rectangle(ansx3, ansy3, ansx4, ansy4);

                    cout << "! " << ansx1 + 1 << " " << ansy1 + 1 << " " << ansx2 << " " << ansy2 <<" "
                    << ansx3 + 1 << " " << ansy3 + 1 << " " << ansx4 << " " << ansy4 << "n"; fflush(stdout);
                    exit(0);
                }
                else if(op == 0){
                    x2 = mid;
                    mid = (x1 + x2) / 2;
                    cout << "? " << 1 << " " << 1 << " " << mid << " " << n << "n"; fflush(stdout);
                }
            }
            else if(op == 0){
                x1 = mid;
                mid = (x1 + x2) / 2;
                cout << "? " << 1 << " " << 1 << " " << mid << " " << n << "n"; fflush(stdout);
            }
        }
    //}


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx