CF1715F Crop Squares

· · 题解

CF1715F Crop Squares

说在前面

你可以每看完一个 Hint 过后进行思考，如果想不出来或者代码无法通过再看下面一个 Hint，而不是看到题目直接把这篇题解冲完。

Hint 1

考虑像下图一样构造多边形：

Hint 2

如 Hint 1，对于答案的 y 值和重叠面积 s_0，有一定的函数关系，一个 y 对应一个 s_0，一个 s_0 对应一个 y。

换言之，同一 y 值得到的重叠面积相同，同一重叠面积得到的 y 值相同，

Hint 3

容易得到，重叠面积是一个 \frac{y}{m}\times 1 的矩形加上一个 \frac{1}{m}\times1 的直角三角形，即，s_0=\frac{y+0.5}{m}，稍微变化下形式即可得到 y=s_0m-0.5。

证明略，运用相似即可。

Hint 4

同理的锯齿状，横着询问，对于重叠面积 s_1 同理得到 x=s_1n-0.5。

这样，在两次询问内，我们就得到了答案的 x,y。

Hint 5（一些细节）

注意到这样的锯齿状不被认为是封闭的多边形，所以我们可以将这些点稍微下调 10^{-7} 个单位长度即可：

如图，橙色的点下调即可。（横式同理）

当然，还有别的解决方案，可以保证精度，即：（图片来源：官方题解）

Solution

对于 C++ 语言，cout << endl 会自动刷新缓存，所以可以不使用 cout << flush。

本题的询问次数很少，所以你刷不刷新都没关系。

AC link

void query(int x, int y, long double &d, bool opt) {
    printf("? %d\n", 2 * x + 2);
    for(int i = 0; i < x; i++) {
        int tx = i, ty = 0, ttx = i, tty = y;
        if(opt) {
            printf("%d %d\n", ty, tx);
            printf("%d %d.99999999\n", tty, ttx);
        }
        else {
            printf("%d %d\n", tx, ty);
            printf("%d.99999999 %d\n", ttx, tty);
        }
    }
    if(opt) printf("%d %d\n%d %d\n", y, x, y, 0);
    else printf("%d %d\n%d %d\n", x, y, 0, y);
    cin >> d;

    return ;
}
signed main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    long double s0, s1;
    query(n, m, s0, 0);
    query(m, n, s1, 1);
    printf("! %.8Lf %.8Lf\n", s1 * n - 0.5, s0 * m - 0.5);
    return 0;
}