結果

問題 No.3018 目隠し宝探し
ユーザー じきお。じきお。
提出日時 2025-01-25 15:54:28
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,366 bytes
コンパイル時間 3,801 ms
コンパイル使用メモリ 279,896 KB
実行使用メモリ 25,972 KB
平均クエリ数 1.95
最終ジャッジ日時 2025-01-25 23:49:11
合計ジャッジ時間 6,933 ms
ジャッジサーバーID
(参考情報)
judge3 / judge12
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample WA * 1
other AC * 6 WA * 15
権限があれば一括ダウンロードができます

ソースコード

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 {
cout << "? " << 1 << " " << 1 << endl;
int d1;
cin >> d1;
cout << "? " << 1 << " " << W << endl;
int d2;
cin >> d2;
Circle<ld> C1(Point<ld>(1, 1), d1), C2(Point<ld>(1, W), d2);
auto res = cross_point(C1, C2);
for (auto [x, y] : res) {
if (x < 1 || y < 1 || x > H || y > W) continue;
int ansx = round(x), ansy = round(y);
cout << "! " << ansx << " " << ansy << endl;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0