This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "nice_lines.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
#define double long double
struct line{
double a,b; //ensure that a^2+b^2=1, i.e. norm vec
double r;
line(double A,double B){
double g=sqrtl(A*A+1);
a=-A/g,b=1.0/g;
r=B/g;
}
double dist(double x,double y){
return fabsl(a*x+b*y-r);
}
};
vector<line> ans;
const double EPS=1e-8;
const double Y=69.420177013;
#define di pair<double,int>
vector<di> v;
double grad(double X){
return (query(X+EPS,Y)-query(X,Y))/EPS;
}
double grad2(double X){
return (query(X,Y+EPS)-query(X,Y))/EPS;
}
vector<signed> ansA,ansB;
void rec(double l,double r,double gl,double gr){
if (r-l<1e-5){
double g=grad2(r)-grad2(l);
//cout<<l<<" "<<r<<" "<<g<<endl;
double best=1e9;
int idx=-1e9;
for (auto [a,b]:v){
if (fabsl(a-g)<best){
best=fabsl(a-g);
idx=b;
}
}
ansA.pub(idx);
ansB.pub(roundl(Y-l*idx));
ans.pub({ansA.back(),ansB.back()});
}
else{
double m=(l+r)/2;
double g=grad(m);
if (fabsl(gl-g)>1e-2) rec(l,m,gl,g);
if (fabsl(gr-g)>1e-2) rec(m,r,g,gr);
}
}
void solve(signed subtask_id, signed N) {
cout<<fixed<<setprecision(12);
for (int x=1;x<=10000;x++){
v.pub({-2.0/sqrtl(1+x*x),x});
v.pub({2.0/sqrtl(1+x*x),-x});
}
rec(-10100,10100,grad(-10100),grad(10100));
if (sz(ansA)!=N){
double y=query(0,-10000);
for (auto it:ans) y-=it.dist(0,-10000);
ansA.pub(0);
ansB.pub(roundl(y-10000));
}
the_lines_are(ansA,ansB);
}
Compilation message (stderr)
nicelines.cpp: In function 'void rec(long double, long double, long double, long double)':
nicelines.cpp:75:21: warning: narrowing conversion of 'ansA.std::vector<int>::back()' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
75 | ans.pub({ansA.back(),ansB.back()});
| ~~~~~~~~~^~
nicelines.cpp:75:33: warning: narrowing conversion of 'ansB.std::vector<int>::back()' from '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} to 'long double' [-Wnarrowing]
75 | ans.pub({ansA.back(),ansB.back()});
| ~~~~~~~~~^~
# | 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... |