結果
問題 | No.3018 目隠し宝探し |
ユーザー |
![]() |
提出日時 | 2025-01-25 16:02:05 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,604 bytes |
コンパイル時間 | 2,905 ms |
コンパイル使用メモリ | 280,096 KB |
実行使用メモリ | 25,948 KB |
平均クエリ数 | 2.68 |
最終ジャッジ日時 | 2025-01-25 23:50:10 |
合計ジャッジ時間 | 6,233 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 |
other | AC * 6 WA * 15 |
ソースコード
#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^62ll integer_sqrt(ll N) {// √N < 2^31ll 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 = bif (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);// cin >> d1;cout << "? " << 1 << " " << W << endl;int d2 = (local_x - 1) * (local_x - 1) + (local_y - W) * (local_y - W);// 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;}}}