QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#167752#6414. Classical Maximization ProblemrealIyxiang#WA 1ms3736kbC++143.1kb2023-09-07 17:08:422023-09-07 17:08:43

Judging History

你现在查看的是最新测评结果

  • [2023-09-07 17:08:43]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3736kb
  • [2023-09-07 17:08:42]
  • 提交

answer

#include <bits/stdc++.h>

#define eb emplace_back
#define ep emplace
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 1e6 + 10;
const db eps = 1e-7;
const db tps = 1e-12;

bool cqu(db x, db y) { return fabs(x - y) < eps; }

struct ve {
	db x, y, z;
	ve(db _x, db _y, db _z) : x(_x), y(_y), z(_z) { }
	db len() { return sqrt(x * x + y * y + z * z); }
	friend ve operator - (ve a, ve b) { return ve(a.x - b.x, a.y - b.y, a.z - b.z); }
	friend ve operator + (ve a, ve b) { return ve(a.x + b.x, a.y + b.y, a.z + b.z); }
	friend ve operator * (ve a, db b) { return ve(a.x * b, a.y * b, a.z * b); }
	friend bool operator == (ve a, ve b) {
		return cqu(a.x, b.x) & cqu(a.y, b.y) & cqu(a.z, b.z);
	}
	void set1() { db t = len(); t = 1 / t; x *= t, y *= t, z *= t; }
};

void solve() {
	ve t(0, 0, 0); t.x = in, t.y = in, t.z = in;
	vector < pair < db, ve > > ans;
	auto output = [&]() {
		printf("%d\n", ans.size());
		ve cur(0, 0, 0);
		for(auto v : ans) {
			if(v.fi < 0) continue;
			ve t = (v.se - cur); db le = min(t.len(), v.fi); t.set1();
			cur = cur + t * le;
			assert(v.fi >= 0 && v.fi <= 10000);
		} //cerr << "!" << cur.x << " " << cur.y << " " << cur.z << endl;
		for(auto v : ans) printf("%.0lf %.0lf %.0lf %.11lf\n", v.se.x, v.se.y, v.se.z, min(1e4, v.fi));
	};
	ve g1(255 + tps, 255 + tps, 255 + tps);
	if(g1 == t) return output();
	auto dt = [&](db x) { return cqu(x, 0) ? 1e4 : x; };
	ve p = g1 - t; p.set1();
	db ret = min({ dt(t.x / p.x), dt(t.y / p.y), dt(t.z / p.z) });
	if(cqu(ret, 1e4) || cqu(t.x, 0) || cqu(t.y, 0) || cqu(t.z, 0)) { }
	else {
		ans.eb(ret, g1); // reverse pos
		t = t - p * ret;
		//cerr << "!" << t.x << " " << t.y << " " << t.z << endl;
	}
	ve g2 = g1;
	if(cqu(t.x, 0)) g2.x = tps; if(cqu(t.y, 0)) g2.y = tps; if(cqu(t.z, 0)) g2.z = tps;
	//if(t == ve(0, 0, 0)) return output();
	p = g2 - t; p.set1();
	ret = min({ dt(t.x / p.x), dt(t.y / p.y), dt(t.z / p.z) });
	if(cqu(ret, 1e4)) { }
	else {
		ans.eb(ret, g2);
		t = t - p * ret;
		//cerr << "!" << t.x << " " << t.y << " " << t.z << endl;
	}
	ve g3 = g2;
	if(cqu(t.x, 0)) g3.x = tps; if(cqu(t.y, 0)) g3.y = tps; if(cqu(t.z, 0)) g3.z = tps;
	ans.eb(t.len(), g3);
	g3.set1();
	t = t - g3 * ans.back().fi;
	reverse(ans.begin(), ans.end()); output();
}

int main() {
#ifdef YJR_2333_TEST
	freopen("1.in", "r", stdin);
#endif
	for(int T = in; T; T--) solve(); return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3736kb

input:

3
2
0 0
0 1
1 0
1 1
2
0 0
0 1
0 2
0 3
2
0 0
1 1
2 2
3 3

output:

2
0 0 0 0.00000000000
255 0 0 2.00000000000
2
0 0 0 0.00000000000
0 255 255 1.41421356237
2
0 0 0 0.00000000000
0 255 255 1.41421356237

result:

wrong answer Integer parameter [name=a[1]] equals to 0, violates the range [1, 4] (test case 1)