Submission #828514

#	Time	Username	Problem	Language	Result	Execution time	Memory
828514		rainboy	Nicelines (RMI20_nicelines)	C11	0 / 100	5 ms	208 KiB

nicelines

#include "nice_lines_c.h"
 
#define N	100
#define M	10000
#define X	1000000
#define Y	((long long) M * X + M + 1)
#define eps	1e-6
 
typedef long double ld;
 
ld abs_(ld a) { return a > 0 ? a : -a; }
ld max(ld a, ld b) { return a > b ? a : b; }
ld error(ld a, ld b) { return abs_(a - b) / max(abs_(b), 1); }

int aa[N], bb[N], n;

void solve_(ld ul, ld vl, ld ur, ld vr) {
	ld z1, z2, u, v; 
	long long y, a, b;

	y = (vr - vl) / (ul - ur) + 0.5;
	z1 = query(X, y), z2 = query(X, y + 1);
	u = z2 - z1, v = z1 - u * y;
	if (error(u, ul) < eps || error(u, ur) < eps) {
		a = y / X, b = y - a * X;
		while (b < -M)
			a--, b += X;
		while (b > M)
			a++, b -= X;
		aa[n] = a, bb[n] = b, n++;
		return;
	}
	solve_(ul, vl, u, v), solve_(u, v, ur, vr);
}

void solve(int subtask_id, int n_) {
	ld ul, vl, ur, vr, z1, z2;

	z1 = query(X, -Y - 1), z2 = query(X, -Y);
	ul = z2 - z1, vl = z2 - ul * -Y;
	z1 = query(X, Y), z2 = query(X, Y + 1);
	ur = z2 - z1, vr = z1 - ur * Y;
	n = 0, solve_(ul, vl, ur, vr);
	the_lines_are(aa, bb);
}

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