Submission #403008

#	Time	Username	Problem	Language	Result	Execution time	Memory
403008		maximath_1	Nicelines (RMI20_nicelines)	C++11	50 / 100	8 ms	384 KiB

nicelines

#include <bits/stdc++.h>
#include "nice_lines.h"
using namespace std;

#define ll long long
#define ld long double
const ld eps = 1e-6;
const ll lim = 10000;
const ll x0 = 2 * lim + 1;
const ll inf = lim * lim * 2 + lim * lim;

map<ll, ld> mem;
ld que(ll y){
	if(mem.count(y)) return mem[y];
	return mem[y] = query(x0, (ld)y / 2.0L);
}

pair<ld, ld> get_line(pair<ld, ld> p1, pair<ld, ld> p2){
	return make_pair((p1.second - p2.second) / (p1.first - p2.first), p1.second - p1.first * (p1.second - p2.second) / (p1.first - p2.first));
}

ld intersectionX(pair<ld, ld> l1, pair<ld, ld> l2){
	return (l2.second - l1.second) / (l1.first - l2.first);
}

bool check_eq(ld a, ld b){
	return fabs(a - b) < eps;
}

bool oneline(ll x1, ll x2, ll x3){
	if(x1 == x2 || x2 == x3 || x3 == x1) return true;
	ld y1 = que(x1), y2 = que(x2), y3 = que(x3);
	return check_eq((y2 - y1)/(x2 - x1), (y3 - y2)/(x3 - x2));
}

set<ll> changing_points;
void dnc(ll lf1, ll lf2, ll rg1, ll rg2){
	pair<ld, ld> l_lf = get_line(make_pair(lf1, que(lf1)), make_pair(lf2, que(lf2)));
	pair<ld, ld> l_rg = get_line(make_pair(rg1, que(rg1)), make_pair(rg2, que(rg2)));
	if(check_eq(l_lf.first, l_rg.first)) return;

	ll md = round(intersectionX(l_lf, l_rg));

	if(oneline(lf1, lf2, md) && oneline(md, rg1, rg2)){
		changing_points.insert(md);
	}else{
		dnc(lf1, lf2, md - 1, md);
		dnc(md - 1, md, rg1, rg2);
	}
}

void solve(int subtask_id, int N){
	dnc(2 * (-inf), 2 * (-inf + x0), 2 * inf, 2 * (inf + x0));

	vector<int> a, b;
	for(auto y : changing_points){
		y /= 2;
		ll bb = y % x0;
		while(bb < -lim) bb += x0;
		while(bb > lim) bb -= x0;

		ll aa = (y - bb) / x0;

		a.push_back(aa);
		b.push_back(bb);
	}

	the_lines_are(a, b);
}

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