A. Archaeology

本场的计算几何题。考虑 ∠ARB<90∘\angle ARB\lt 90^\circ 的等价条件，先连线 RBRB，然后过 RR 做 RBRB 垂线，则 AA 点和 BB 点应该在这条直线的同侧（即直线左半平面所记录的区域）。

也就是说，每次询问都可以用一条直线，把 AA 可能所在的区域变小一点。诶？多个半平面的交集，这不就是半平面交吗！诶，那么 9090 次的限制呢？我们每次让这个面积缩小一半不就是二分了吗！log⁡21018<90\log_2 10^{18}\lt 90 诶正好！

那么怎么让这个面积缩小一半呢？我们可以维护半平面交形成的凸包的最小覆盖矩形（其实只需要 min⁡x,min⁡y,max⁡x,max⁡y\min x,\min y,\max x, \max y 这四个值，然后构造矩形即可），然后询问中心，询问到的新点继续分割半平面交出来的凸包。

Code

需要注意的实现细节：

  1. 可以在一开始加入四条直线把 [1,N]×[1,N][1,N]\times [1,N] 的矩形全部包住，避免半平面交没有封闭从而需要讨论
  2. 可能需要特殊讨论 n=1n=1 的情况
  3. 可能会出现新加入的直线并没有“切掉”凸包或者只“切掉”一点点凸包。为了避免这种情况下反复询问某个点，这里额外计算了两次凸包面积减少了多少。如果小于 10%10\%，那么挑选相邻的点进行询问。
  4. x,yx,y 上下取整都可以
  5. 当剩余的格点数量少于剩余询问次数时，直接 break 暴力询问过去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include "geometry/halfplane.hpp"
#include "geometry/line.hpp"
#include "geometry/real.hpp"
#include "geometry/vec.hpp"
#include <iostream>
#include <tuple>
#include <vector>
using namespace geometry;
using i64 = long long;

int n, steps = 90;
std::vector<line> lines;
polygon poly;
bool verdict;

int main() {
    std::cin >> n;
    if (n == 1) {
        std::cout << "1 1" << std::endl;
        int rx, ry;
        std::cin >> rx >> ry;
        return 0;
    }

    double tn = n;
    lines.push_back(from_points(vec{1, 1}, vec{tn, 1}));
    lines.push_back(from_points(vec{tn, 1}, vec{tn, tn}));
    lines.push_back(from_points(vec{tn, tn}, vec{1, tn}));
    lines.push_back(from_points(vec{1, tn}, vec{1, 1}));

    i64 l = 1e18, r = -1e18, u = -1e18, d = 1e18;
    double pa = -1;

    while (steps) {
        std::tie(lines, poly, verdict) = solve_halfplane(lines);
        double a                       = area(poly);
        double ratio                   = (pa - a) / pa * 100;
        l = 1e18, r = -1e18, u = -1e18, d = 1e18;
        for (auto [x, y] : poly) {
            l = min(l, std::round(x));
            r = max(r, std::round(x));
            u = max(u, std::round(y));
            d = min(d, std::round(y));
        }

        i64 rem = (r - l + 1) * (u - d + 1);
        if (rem <= steps) break;

        i64 x = (l + r + 1) / 2, y = (u + d + 1) / 2, rx, ry;
        if (sign(pa, -1) != 0 && sign(ratio, 10) <= 0) {
            i64 tx = x, ty = y;
            while (tx == x && ty == y) {
                x += rand() % 3 - 1;
                y += rand() % 3 - 1;
            }
        }
        std::cout << x << " " << y << std::endl;
        steps--;
        std::cin >> rx >> ry;

        if (x == rx && y == ry) return 0;
        i64 dx = rx - x, dy = ry - y;
        i64 ddx = dy, ddy = -dx;

        lines.push_back(from_points(vec{x * 1.0, y * 1.0}, vec{1.0 * (x + ddx), 1.0 * (y + ddy)}));
        pa = a;
    }

    for (int i = l; i <= r; i++) {
        for (int j = d; j <= u; j++) {
            std::cout << i << " " << j << std::endl;
            steps--;
            if (steps < 0) return 0;
            int rx, ry;
            std::cin >> rx >> ry;
            if (rx == i && ry == j) return 0;
        }
    }
}