QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134302#2290. Kinking Cablesmshcherba#RE 1ms3852kbC++172.6kb2023-08-03 16:47:302023-08-03 16:47:32

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 16:47:32]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3852kb
  • [2023-08-03 16:47:30]
  • 提交

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;
	Point p(0, 0), last(n, m);
	vector<Point> ans;
	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 ((cur - p).len() + (last - cur).len() <= l) {
				l -= (cur - p).len();
				p = cur;
				ans.push_back(p);
			}
			else if ((Point(n, m - 1) - p).len() + 1 <= l) {
				assert((Point(n, 0) - p).len() + m > l - EPS);
				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 {
				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));
				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 (const Point& pi : ans) {
		assert(pi.x > -EPS && pi.x < n + EPS && pi.y > -EPS && pi.y < m + EPS);
		cout << pi.x << " " << pi.y << "\n";
	}
	db ul = 0;
	FOR(i, 0, SZ(ans) - 1) {
		ul += (ans[i + 1] - ans[i]).len();
	}
	cerr << ul << endl;
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

79 78
1980.7712136406

output:

52
0.0000000000 0.0000000000
0.0000000000 77.0000000000
1.0000000000 77.0000000000
1.0000000000 0.0000000000
2.0000000000 0.0000000000
2.0000000000 77.0000000000
3.0000000000 77.0000000000
3.0000000000 0.0000000000
4.0000000000 0.0000000000
4.0000000000 77.0000000000
5.0000000000 77.0000000000
5.000...

result:

ok correct

Test #2:

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

input:

33 65
1947.7601065763

output:

62
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: 3832kb

input:

51 51
555.0803652025

output:

22
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: -100
Dangerous Syscalls

input:

49 2
67.3588717350

output:


result: