Submission #943393

#TimeUsernameProblemLanguageResultExecution timeMemory
943393huutuanNicelines (RMI20_nicelines)C++14
31 / 100
10 ms1308 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))}; } const int X=3e4; void solve(int subtask_id, int N) { vector<int> va, vb; vector<long double> diff; for (int i=0; i<=(int)X; ++i) diff.push_back((long double)2/sqrtl(i*i+1)); auto insert_line=[&](int x){ int b=x%X; if (b<0) b+=X; if (b>1e4) b-=X; int a=(x-b)/X; va.push_back(a); vb.push_back(b); }; map<int, long double> memo; auto fake_query=[&](int x) -> long double { if (memo.count(x)) return memo[x]; return memo[x]=query(X, x); }; auto get_slope=[&](int x) -> long double { return fake_query(x+1)-fake_query(x); }; auto dnc=[&](auto self, int l, int r, long double sl, long double sr){ if (l==r || abs(sr-sl)<1e-5) return; for (auto &x:diff){ if (abs(sr-sl-x)<eps){ long double t1=fake_query(l), t2=fake_query(r); insert_line(round((t2-t1+l*sl-r*sr)/(sl-sr))); return; } } if (l+1==r){ insert_line(r); return; } int mid=(l+r)>>1; long double smid=get_slope(mid); self(self, l, mid, sl, smid); self(self, mid, r, smid, sr); }; long double l=-3.3e8-1, r=3.3e8+1; dnc(dnc, l, r, get_slope(l), get_slope(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...