이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "nice_lines.h"
#include <bits/stdc++.h>
using namespace std;
template <class T>
struct Point
{
T x, y;
Point(T _x = 0, T _y = 0)
{
x = _x;
y = _y;
}
bool operator<(Point a) { return tie(x, y) < tie(a.x, a.y); }
bool operator==(Point a) { return tie(x, y) == tie(a.x, a.y); }
Point operator+(Point a) { return Point(x + a.x, y + a.y); }
Point operator-(Point a) { return Point(x - a.x, y - a.y); }
Point operator*(T a) { return Point(x * a, y * a); }
Point operator/(T a) { return Point(x / a, y / a); }
T dot(Point a) { return x * a.x + y * a.y; }
T dot(Point a, Point b) { return (a - *this).dot(b - *this); }
T cross(Point a) { return x * a.y - y * a.x; }
T cross(Point a, Point b) { return (a - *this).cross(b - *this); }
T dist2() { return x * x + y * y; }
long double dist() { return sqrt(dist2()); }
};
const long double eps = 1e-7;
using pt = Point<long double>;
long double line_point_dist(pt a, pt b, pt c)
{
return abs(a.cross(b, c)) / (a - b).dist();
}
mt19937 rng(69420);
long double rand(long double l, long double r)
{
return uniform_real_distribution<long double>(l, r)(rng);
}
pair<int, int> line_from_points(pt a, pt b)
{
long double slope = round((b.y - a.y) / (b.x - a.x));
return {(int)(round(slope)), (int)(round(a.y - a.x * slope))};
}
void solve(int subtask_id, int N)
{
auto f = [&](long double t) -> long double
{
return query(3e4, t);
};
vector<int> va, vb;
auto dnc = [&](auto self, long double l, long double r, long double fl, long double fr)
{
long double mid = (l + r) / 2;
long double fmid = f(mid);
if (abs((fl + fr) / 2 - fmid) < eps)
return;
if ((r - l) < 1)
{
long double c = (f(r + 0.1) - fr - fl + f(l - 0.1)) / 2;
long double d = sqrtl(max<long double>(0.0, 0.1 * 0.1 - c * c));
int a = round(d / c);
if (mid < -eps)
a = -a;
int b = round(mid - (3e4) * a);
va.push_back(a);
vb.push_back(b);
return;
}
self(self, l, mid, fl, fmid);
self(self, mid, r, fmid, fr);
return;
};
long double l = -3e8 - 2e4 + rand(1, 10), r = 3e8 + 2e4 - rand(1, 10);
dnc(dnc, l, r, f(l), f(r));
the_lines_are(va, vb);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |