結果

問題 No.3018 目隠し宝探し
ユーザー じきお。
提出日時 2025-01-25 16:03:13
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 78 ms / 2,000 ms
コード長 5,639 bytes
コンパイル時間 2,863 ms
コンパイル使用メモリ 280,164 KB
実行使用メモリ 25,972 KB
平均クエリ数 2.68
最終ジャッジ日時 2025-01-25 23:50:20
合計ジャッジ時間 5,688 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...)
#endif

// N は平方数, 0 <= N <= 4.5*10^18 < 2^62
ll integer_sqrt(ll N) {
    // √N < 2^31
    ll low = -1, high = 1LL << 31;
    while (high - low > 1) {
        ll mid = (low + high) / 2, mid2 = mid * mid;
        if (mid2 <= N) {
            low = mid;
        } else {
            high = mid;
        }
    }
    return low;
}

using ld = long double;
constexpr ld EPS = 1e-10;
const ld PI = acos(-1);

bool equals(ld a, ld b) { return abs(b - a) < EPS; }
int sign(ld a) { return equals(a, 0) ? 0 : (a > 0 ? 1 : -1); }

template <class R>
struct Point {
    R x, y;
    Point() : x(0), y(0) {}
    Point(R x0, R y0) : x(x0), y(y0) {}
    template <class T, class U>
    Point(const pair<T, U>& p) : x(p.first), y(p.second) {}

    Point operator-() const { return Point(-x, -y); }
    Point operator+(const Point& p) const { return Point(*this) += p; }
    Point operator-(const Point& p) const { return Point(*this) -= p; }
    Point operator*(const R& k) const { return Point(*this) *= k; }
    Point operator/(const R& k) const { return Point(*this) /= k; }
    Point& operator+=(const Point& p) {
        x += p.x, y += p.y;
        return *this;
    }
    Point& operator-=(const Point& p) {
        x -= p.x, y -= p.y;
        return *this;
    }
    Point& operator*=(const R& k) {
        x *= k, y *= k;
        return *this;
    }
    Point& operator/=(const R& k) {
        x /= k, y /= k;
        return *this;
    }
    bool operator<(const Point& p) const { return x != p.x ? x < p.x : y < p.y; }
    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return !(*this == p); }
    Point rotate(ld theta) const { return Point(x * cos(theta) - y * sin(theta), x * sin(theta) + y * cos(theta)); }
    friend R dot(const Point& p, const Point& q) { return p.x * q.x + p.y * q.y; }
    friend R cross(const Point& p, const Point& q) { return p.x * q.y - p.y * q.x; }
    friend R norm(const Point& p) { return dot(p, p); }
    friend ld abs(const Point& p) { return sqrt(norm(p)); }
    friend ld arg(const Point& p) { return atan2(p.y, p.x); }
    friend Point round(const Point& p) { return Point(round(p.x), round(p.y)); }
    friend istream& operator>>(istream& is, Point& p) { return is >> p.x >> p.y; }
    friend ostream& operator<<(ostream& os, const Point& p) { return os << p.x << " " << p.y; }
};
// a - b - c の位置関係
template <class R>
int ccw(const Point<R>& a, const Point<R>& b, const Point<R>& c) {
    Point x = b - a, y = c - a;
    if (cross(x, y) > EPS) return +1;                 // a - b - c が反時計回り(a - b から見て c が左側)
    if (cross(x, y) < -EPS) return -1;                // a - b - c が時計回り(a - b から見て c が右側)
    if (min(norm(x), norm(y)) < EPS * EPS) return 0;  // c = a または c = b
    if (dot(x, y) < EPS) return +2;                   // c - a - b の順で一直線
    if (norm(x) < norm(y)) return -2;                 // a - b - c の順で一直線
    return 0;                                         // a - c - b の順で一直線
}

// 円
template <class R>
struct Circle {
    Point<R> p;
    R r;
    Circle() = default;
    Circle(const Point<R>& p0, R r0) : p(p0), r(r0) {}
};
// 円の交差判定
template <class R>
int intersect(Circle<R>& C1, Circle<R>& C2) {
    if (C1.r < C2.r) swap(C1, C2);
    R d = abs(C1.p - C2.p);
    if (C1.r + C2.r < d) return 4;         // 離れている
    if (equals(C1.r + C2.r, d)) return 3;  // 外接
    if (C1.r - C2.r < d) return 2;         // 交わる
    if (equals(C1.r - C2.r, d)) return 1;  // 内接
    return 0;                              // 内包
}
// 円の交点
template <class R>
vector<Point<R>> cross_point(Circle<R>& C1, Circle<R>& C2) {
    if (intersect(C1, C2) == 0 || intersect(C1, C2) == 4) return {};
    vector<Point<R>> res;
    R d = abs(C1.p - C2.p);
    R a = acos((C1.r * C1.r + d * d - C2.r * C2.r) / (2 * C1.r * d));
    R t = arg(C2.p - C1.p);
    res.emplace_back(C1.p + Point<R>(cos(t + a) * C1.r, sin(t + a) * C1.r));
    res.emplace_back(C1.p + Point<R>(cos(t - a) * C1.r, sin(t - a) * C1.r));
    return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int H, W;
    cin >> H >> W;

    if (H == 1 && W == 1) {
        cout << "! " << H << " " << W << endl;
    } else if (H == 1) {
        cout << "? " << 1 << " " << 1 << endl;
        int d;
        cin >> d;
        cout << "! " << 1 << " " << integer_sqrt(d) + 1 << endl;
    } else if (W == 1) {
        cout << "? " << 1 << " " << 1 << endl;
        int d;
        cin >> d;
        cout << "! " << integer_sqrt(d) + 1 << " " << 1 << endl;
    } else {
        // int local_x = 1, local_y = 3;
        cout << "? " << 1 << " " << 1 << endl;
        // int d1 = (local_x - 1) * (local_x - 1) + (local_y - 1) * (local_y - 1);
        int d1;
        cin >> d1;
        cout << "? " << 1 << " " << W << endl;
        // int d2 = (local_x - 1) * (local_x - 1) + (local_y - W) * (local_y - W);
        int d2;
        cin >> d2;
        Circle<ld> C1(Point<ld>(1, 1), sqrt(d1)), C2(Point<ld>(1, W), sqrt(d2));
        auto res = cross_point(C1, C2);
        debug(res);
        for (auto [x, y] : res) {
            int ansx = round(x), ansy = round(y);
            if (ansx < 1 || ansx > H || ansy < 1 || ansy > W) continue;
            cout << "! " << ansx << " " << ansy << endl;
            return 0;
        }
    }
}
0