QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#134338#2290. Kinking Cablesmshcherba#RE 1ms3928kbC++173.6kb2023-08-03 17:23:172023-08-03 17:23:19

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-03 17:23:19]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3928kb
  • [2023-08-03 17:23:17]
  • 提交

answer

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

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

typedef long double db;

const db EPS = 1e-9;

struct Point {
	db x, y;
	Point() {}
	Point(db _x, db _y): x(_x), y(_y) {}
	Point operator+(const Point& p) const {
		return {x + p.x, y + p.y};
	}
	Point operator-(const Point& p) const {
		return {x - p.x, y - p.y};
	}
	db operator*(const Point& p) const {
		return x * p.y - p.x * y;
	}
	db d2() const {
		return x * x + y * y;
	}
	db len() const {
		return sqrt(d2());
	}
	Point scale(db l) const {
		l /= len();
		return Point(x * l, y * l);
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int n, m;
	db l;
	cin >> n >> m >> l;
	bool sw = n > m;
	if (sw) {
		swap(n, m);
	}
	db l0 = l;
	Point p(0, 0), last(n, m);
	vector<Point> ans = {{0, 0}};
	vector<int> ys(m);
	iota(ALL(ys), 0);
	FOR(i, 0, n) {
		for (int j : ys) {
			if (l < -1) {
				break;
			}
			Point cur(i, j);
			if ((Point(n, m - 1) - p).len() + 1 < l + EPS && (Point(n, 0) - p).len() + m > l - EPS) {
				cerr << "a" << endl;
				double low = 0, high = m - 1;
				FOR(it, 0, 74) {
					double mid = (low + high) / 2;
					if ((Point(n, mid) - p).len() + m - mid < l) {
						high = mid;
					}
					else {
						low = mid;
					}
				}
				ans.emplace_back(n, low);
				ans.emplace_back(last);
				l = -47;
			}
			else if ((Point(n - 1, m) - p).len() + 1 < l + EPS && (Point(i, m) - p).len() + n > l - EPS) {
				cerr << "b" << endl;
				double low = i, high = n - 1;
				FOR(it, 0, 74) {
					double mid = (low + high) / 2;
					if ((Point(mid, m) - p).len() + n - mid < l) {
						high = mid;
					}
					else {
						low = mid;
					}
				}
				ans.emplace_back(low, m);
				ans.emplace_back(last);
				l = -47;
			}
			else if ((cur - p).len() + (last - cur).len() < l + EPS) {
				l -= (cur - p).len();
				p = cur;
				ans.push_back(p);
			}
			else {
				cerr << "c" << endl;
				Point mid = p + last;
				mid.x /= 2;
				mid.y /= 2;
				Point v(p.y - last.y, last.x - p.x);
				db len = sqrt(max((db)0, l * l - (last - p).d2())) / 2;
				ans.push_back(mid + v.scale(len));
				if (ans.back().x < -EPS || ans.back().x > n + EPS || ans.back().y < -EPS || ans.back().y > m + EPS) {
					cerr << ans.back().x << " " << ans.back().y << endl;
					ans.pop_back();
					ans.push_back(mid - v.scale(len));
				}
				ans.push_back(last);
				l = -47;
			}
		}
		reverse(ALL(ys));
	}
	vector<Point> newAns;
	for (const Point & pi : ans) {
		if (SZ(newAns) > 1 && abs((newAns.back() - newAns[SZ(newAns) - 2]) * (pi - newAns.back())) / (pi - newAns.back()).len() < EPS) {
			newAns.pop_back();
		}
		newAns.push_back(pi);
	}
	ans = newAns;
	cout << SZ(ans) << "\n";
	for (Point& pi : ans) {
		assert(pi.x > -EPS && pi.x < n + EPS && pi.y > -EPS && pi.y < m + EPS);
		if (sw) {
			swap(pi.x, pi.y);
		}
		cout << pi.x << " " << pi.y << "\n";
	}
	db ul = 0;
	FOR(i, 0, SZ(ans) - 1) {
		ul += (ans[i + 1] - ans[i]).len();
	}
	assert(abs(ul - l0) / l0 < 1e-6);
	FOR(i, 0, SZ(ans)) {
		FOR(j, 0, i) {
			assert((ans[j] - ans[i]).len() > 1 - EPS);
		}
	}
	assert(SZ(ans) <= 500);
	cerr << ul << endl;
	return 0;
}


详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3928kb

input:

79 78
1980.7712136406

output:

48
0.0000000000 0.0000000000
78.0000000000 0.0000000000
78.0000000000 1.0000000000
0.0000000000 1.0000000000
0.0000000000 2.0000000000
78.0000000000 2.0000000000
78.0000000000 3.0000000000
0.0000000000 3.0000000000
0.0000000000 4.0000000000
78.0000000000 4.0000000000
78.0000000000 5.0000000000
0.000...

result:

ok correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 3900kb

input:

33 65
1947.7601065763

output:

60
0.0000000000 0.0000000000
0.0000000000 64.0000000000
1.0000000000 64.0000000000
1.0000000000 0.0000000000
2.0000000000 0.0000000000
2.0000000000 64.0000000000
3.0000000000 64.0000000000
3.0000000000 0.0000000000
4.0000000000 0.0000000000
4.0000000000 64.0000000000
5.0000000000 64.0000000000
5.000...

result:

ok correct

Test #3:

score: 0
Accepted
time: 1ms
memory: 3888kb

input:

51 51
555.0803652025

output:

20
0.0000000000 0.0000000000
0.0000000000 50.0000000000
1.0000000000 50.0000000000
1.0000000000 0.0000000000
2.0000000000 0.0000000000
2.0000000000 50.0000000000
3.0000000000 50.0000000000
3.0000000000 0.0000000000
4.0000000000 0.0000000000
4.0000000000 50.0000000000
5.0000000000 50.0000000000
5.000...

result:

ok correct

Test #4:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

49 2
67.3588717350

output:

4
0.0000000000 0.0000000000
10.0000000000 0.0000000000
0.9295032889 2.0000000000
49.0000000000 2.0000000000

result:

ok correct

Test #5:

score: -100
Dangerous Syscalls

input:

37 48
1713.3643608504

output:


result: