제출 #942925

#제출 시각아이디문제언어결과실행 시간메모리
942925vjudge1Nicelines (RMI20_nicelines)C++17
84.01 / 100
42 ms696 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...