Submission #1138643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138643		Math4Life2020	Nicelines (RMI20_nicelines)	C++20	50 / 100	2 ms	432 KiB

nicelines

#include "nice_lines.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ld = long double;
using pii = pair<ll,ll>; using pld = pair<ld,ld>;
mt19937_64 gen;
vector<ll> ans;

ll XQ = 1e3; ld XQd = (ld)XQ;
ll AMAX = 500;
ld EPS = 1e-3;
ld TRD = (1.0L)/3;

// vector<pii> lin;

// ld query(ld x, ld y) {
// 	ld qval = 0;
// 	for (pii p0: lin) {
// 		qval += abs(y-p0.first*x-p0.second)/sqrt(p0.first*p0.first+1);
// 	}
// 	return qval;
// }

bool eq(ld x, ld y) {
	return (abs(x-y)<=EPS);
}

bool eq(pld px, pld py) {
	return (eq(px.first,py.first)&&eq(px.second,py.second));
}

// pld gline(pld px, pld py) { //get line segment
// 	return (pld){(py.second-px.second)/(py.first-px.first),(py.first*px.second-px.first*py.second)/(py.first-px.first)};
// }

// pld gseg(ll x) { //get segment corresponding to interval (x,x+1)
// 	return gline({TRD+x,query(XQd,TRD+x)},{2*TRD+x,query(XQd,2*TRD+x)});
// }

pld gseg(ll x) {
	ld x0 = (ld)x+TRD;
	ld x1 = (ld)x+2*TRD;
	//cout << "x0,x1="<<x0<<","<<x1<<"\n";
	ld y0 = query(XQd,x0);
	ld y1 = query(XQd,x1);
	//cout << "y0,y1="<<y0<<","<<y1<<"\n";
	ld yDIF = y1-y0;
	return (pld){(yDIF)/(TRD),(y0*TRD-x0*yDIF)/(TRD)};
}

ld gint(pld px, pld py) {
	return (-(py.second-px.second)/(py.first-px.first));
}

ll flr(ld x0) {
	if (x0>0) {
		return (ll)(x0+EPS);
	} else {
		return -(ll)(EPS-x0);
	}
}

void solvep(pld pl, ll xl, pld pr, ll xr) {
	// cout << "pl="<<pl.first<<","<<pl.second<<"\n";
	// cout << "pr="<<pr.first<<","<<pr.second<<"\n";
	// exit(0);
	if (eq(pl,pr)) {
		return;
	}
	//cout << "gint="<<gint(pl,pr)<<"\n";
	ll xm = flr(gint(pl,pr));
	//cout << "xm="<<xm<<"\n";
	// exit(0);
	assert(xl<=xm);
	assert(xm<=xr);
	pld pm = gseg(xm);
	//cout << "pm="<<pm.first<<","<<pm.second<<"\n";
	if (eq(pl,pm)||eq(pr,pm)) {
		ans.push_back(xm);
	} else {
		// cout << "f1\n";
		// exit(0);
		solvep(pl,xl,pm,xm);
		solvep(pm,xm,pr,xr);
	}
}

void solve(int subtask_id, int N) {
	ans.clear();
	gen = mt19937_64((long long) new char);
	solvep(gseg(-3*AMAX*AMAX),(-3*AMAX*AMAX),gseg(3*AMAX*AMAX),3*AMAX*AMAX);
	vector<int> va,vb;
	for (ll x0: ans) {
		if (x0>AMAX) {
			ll m0 = (x0+AMAX)/XQ;
			va.push_back(m0);
			ll b0 = x0-XQ*m0;
			vb.push_back(b0);
		} else if (x0<(-AMAX)) {
			ll m0 = -((AMAX-x0)/XQ);
			va.push_back(m0);
			ll b0 = x0-XQ*m0;
			vb.push_back(b0);
		} else {
			va.push_back(0);
			vb.push_back(x0);
		}
	}
	the_lines_are(va,vb);
	// assert(va.size()==N);
	// for (ll i=0;i<N;i++) {
	// 	cout << va[i] <<" "<<vb[i]<<"\n";
	// }
}

// int main() {
// 	cout << setprecision(30);
// 	lin.push_back({1,0});
// 	lin.push_back({-5,10});
// 	lin.push_back({20,15});
// 	solve(0,lin.size());
// }

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 19 / 19
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27