oj.uz

Submission #208205

# Submission time Handle Problem Language Result Execution time Memory
208205 2020-03-10T09:25:30 Z E869120 Scissors and Tape (CEOI19_scissors) C++14
30 / 100
 91 ms 93048 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

int N; vector<pair<double, double>> X;
int M; vector<pair<double, double>> Y;

double G;
double ax[1 << 18], ay[1 << 18], bx[1 << 18], by[1 << 18];
double cx[1 << 18], cy[1 << 18], dx[1 << 18], dy[1 << 18]; bool trans[1 << 18];

bool equal(double ap, double bp) {
	if (fabs(ap - bp) < 1.0 / 1200.0) return true;
	if (min(ap, bp) / max(ap, bp) >= 1199.0 / 1200.0) return true;
	return false;
}

void solve(double H1, double W1, double H2, double W2, int idx) {
	if (equal(H1, H2) && equal(W1, W2)) {
		ax[idx] = 0; ay[idx] = 0; bx[idx] = H1; by[idx] = W1;
		cx[idx] = 0; cy[idx] = 0; dx[idx] = H2; dy[idx] = W2;
		trans[idx] = false;
		G = idx;
		return;
	}
	if (H1 == W2 && H2 == W1) {
		ax[idx] = 0; ay[idx] = 0; bx[idx] = H1; by[idx] = W1;
		cx[idx] = 0; cy[idx] = 0; dx[idx] = H2; dy[idx] = W2;
		trans[idx] = true;
		G = idx;
		return;
	}

	double c[4] = { H1, H2, W1, W2 }; sort(c, c + 4);
	double v1 = c[0], v2 = c[2]; if (H1 == v2 || W1 == v1) swap(v1, v2);
	double w1 = v1, w2 = v2;
	if (H2 == v1 || W2 == v2) { trans[idx] = false; }
	if (H2 == v2 || W2 == v1) { trans[idx] = true; swap(w1, w2); }
	
	double c1 = 0, c2 = 0;
	double d1 = 0, d2 = 0;
	if (H1 == v1) {
		ax[idx] = 0; ay[idx] = W1 - v2;
		bx[idx] = H1; by[idx] = W1;
		c1 = H1; c2 = W1 - v2;
	}
	else if (W1 == v2) {
		ax[idx] = H1 - v1; ay[idx] = 0;
		bx[idx] = H1; by[idx] = W1;
		c1 = H1 - v1; c2 = W1;
	}
	if (H2 == w1) {
		cx[idx] = 0; cy[idx] = W2 - w2;
		dx[idx] = H2; dy[idx] = W2;
		d1 = H2; d2 = W2 - w2;
	}
	else if (W2 == w2) {
		cx[idx] = H2 - w1; cy[idx] = 0;
		dx[idx] = H2; dy[idx] = W2;
		d1 = H2 - w1; d2 = W2;
	}

	solve(c1, c2, d1, d2, idx + 1);
}

int main() {
	//FILE* in = freopen("in1.txt", "r", stdin);
	//FILE* out = freopen("out1.txt", "w", stdout);

	// ステップ 1. 入力
	cin >> N; X.resize(N, make_pair(0, 0));
	for (int i = 0; i < N; i++) cin >> X[i].first >> X[i].second;
	cin >> M; Y.resize(M, make_pair(0, 0));
	for (int i = 0; i < M; i++) cin >> Y[i].first >> Y[i].second;

	// ステップ 2. 最大座標を求める
	double px = 0, py = 0; for (int i = 0; i < N; i++) { px = max(px, X[i].first); py = max(py, X[i].second); }
	double qx = 0, qy = 0; for (int i = 0; i < M; i++) { qx = max(qx, Y[i].first); qy = max(qy, Y[i].second); }

	// ステップ 3. 操作を行う
	solve(px, py, qx, qy, 1);

	// ステップ 4. 出力を行う
	cout << "scissors" << endl;
	cout << "0 " << G << endl;
	for (int i = 1; i <= G; i++) {
		cout << 4 << " " << ax[i] << " " << ay[i] << " " << bx[i] << " " << ay[i] << " " << bx[i] << " " << by[i] << " " << ax[i] << " " << by[i] << endl;
	}

	cout << "tape" << endl;
	cout << G; for (double i = 1; i <= G; i++) cout << " " << i; cout << endl;
	for (int i = 1; i <= G; i++) {
		if (trans[i] == false) cout << 4 << " " << cx[i] << " " << cy[i] << " " << dx[i] << " " << cy[i] << " " << dx[i] << " " << dy[i] << " " << cx[i] << " " << dy[i] << endl;
		if (trans[i] == true) cout << 4 << " " << dx[i] << " " << cy[i] << " " << dx[i] << " " << dy[i] << " " << cx[i] << " " << dy[i] << " " << cx[i] << " " << cy[i] << endl;
	}
	cout << 4 << " " << 0 << " " << 0 << " " << qx << " " << 0 << " " << qx << " " << qy << " " << 0 << " " << qy << endl;
	return 0;
}

Compilation message

scissors.cpp:6:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB used 36 vertices, largest error was 0.00000002800000
2 Correct 5 ms 380 KB used 28 vertices, largest error was 0.00000000800000
3 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000001600000
4 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
5 Correct 5 ms 248 KB used 28 vertices, largest error was 0.00000000800000
6 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
7 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
8 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000002500000
9 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000001900000
10 Correct 5 ms 248 KB used 28 vertices, largest error was 0.00000000800000

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB used 76 vertices, largest error was 0.00000002500000
2 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000000800000
3 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000003400000
4 Correct 5 ms 376 KB used 292 vertices, largest error was 0.00000397399997
5 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000006208642
6 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000008810256
7 Correct 5 ms 376 KB used 84 vertices, largest error was 0.00000009211111
8 Correct 5 ms 376 KB used 420 vertices, largest error was 0.00000658916321
9 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000003900000
10 Correct 5 ms 376 KB used 132 vertices, largest error was 0.00000005300000

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB used 36 vertices, largest error was 0.00000002800000
2 Correct 5 ms 380 KB used 28 vertices, largest error was 0.00000000800000
3 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000001600000
4 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
5 Correct 5 ms 248 KB used 28 vertices, largest error was 0.00000000800000
6 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
7 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
8 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000002500000
9 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000001900000
10 Correct 5 ms 248 KB used 28 vertices, largest error was 0.00000000800000
11 Correct 5 ms 380 KB used 76 vertices, largest error was 0.00000002500000
12 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000000800000
13 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000003400000
14 Correct 5 ms 376 KB used 292 vertices, largest error was 0.00000397399997
15 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000006208642
16 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000008810256
17 Correct 5 ms 376 KB used 84 vertices, largest error was 0.00000009211111
18 Correct 5 ms 376 KB used 420 vertices, largest error was 0.00000658916321
19 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000003900000
20 Correct 5 ms 376 KB used 132 vertices, largest error was 0.00000005300000
21 Correct 5 ms 376 KB used 140 vertices, largest error was 0.00001206266664
22 Correct 5 ms 248 KB used 124 vertices, largest error was 0.00000020385384
23 Correct 5 ms 376 KB used 172 vertices, largest error was 0.00000018094929
24 Correct 5 ms 376 KB used 220 vertices, largest error was 0.00000016098469
25 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000005503917
26 Correct 5 ms 376 KB used 108 vertices, largest error was 0.00000004999999
27 Correct 5 ms 376 KB used 196 vertices, largest error was 0.00000011900000
28 Correct 5 ms 376 KB used 220 vertices, largest error was 0.00000080749741
29 Correct 5 ms 376 KB used 132 vertices, largest error was 0.00000017862311
30 Correct 5 ms 376 KB used 84 vertices, largest error was 0.00000122181102

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 93048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 91 ms 93048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB used 36 vertices, largest error was 0.00000002800000
2 Correct 5 ms 380 KB used 28 vertices, largest error was 0.00000000800000
3 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000001600000
4 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
5 Correct 5 ms 248 KB used 28 vertices, largest error was 0.00000000800000
6 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
7 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
8 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000002500000
9 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000001900000
10 Correct 5 ms 248 KB used 28 vertices, largest error was 0.00000000800000
11 Correct 5 ms 380 KB used 76 vertices, largest error was 0.00000002500000
12 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000000800000
13 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000003400000
14 Correct 5 ms 376 KB used 292 vertices, largest error was 0.00000397399997
15 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000006208642
16 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000008810256
17 Correct 5 ms 376 KB used 84 vertices, largest error was 0.00000009211111
18 Correct 5 ms 376 KB used 420 vertices, largest error was 0.00000658916321
19 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000003900000
20 Correct 5 ms 376 KB used 132 vertices, largest error was 0.00000005300000
21 Correct 5 ms 376 KB used 140 vertices, largest error was 0.00001206266664
22 Correct 5 ms 248 KB used 124 vertices, largest error was 0.00000020385384
23 Correct 5 ms 376 KB used 172 vertices, largest error was 0.00000018094929
24 Correct 5 ms 376 KB used 220 vertices, largest error was 0.00000016098469
25 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000005503917
26 Correct 5 ms 376 KB used 108 vertices, largest error was 0.00000004999999
27 Correct 5 ms 376 KB used 196 vertices, largest error was 0.00000011900000
28 Correct 5 ms 376 KB used 220 vertices, largest error was 0.00000080749741
29 Correct 5 ms 376 KB used 132 vertices, largest error was 0.00000017862311
30 Correct 5 ms 376 KB used 84 vertices, largest error was 0.00000122181102
31 Runtime error 85 ms 93048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB used 36 vertices, largest error was 0.00000002800000
2 Correct 5 ms 380 KB used 28 vertices, largest error was 0.00000000800000
3 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000001600000
4 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
5 Correct 5 ms 248 KB used 28 vertices, largest error was 0.00000000800000
6 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
7 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
8 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000002500000
9 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000001900000
10 Correct 5 ms 248 KB used 28 vertices, largest error was 0.00000000800000
11 Correct 5 ms 380 KB used 76 vertices, largest error was 0.00000002500000
12 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000000800000
13 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000003400000
14 Correct 5 ms 376 KB used 292 vertices, largest error was 0.00000397399997
15 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000006208642
16 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000008810256
17 Correct 5 ms 376 KB used 84 vertices, largest error was 0.00000009211111
18 Correct 5 ms 376 KB used 420 vertices, largest error was 0.00000658916321
19 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000003900000
20 Correct 5 ms 376 KB used 132 vertices, largest error was 0.00000005300000
21 Correct 5 ms 376 KB used 140 vertices, largest error was 0.00001206266664
22 Correct 5 ms 248 KB used 124 vertices, largest error was 0.00000020385384
23 Correct 5 ms 376 KB used 172 vertices, largest error was 0.00000018094929
24 Correct 5 ms 376 KB used 220 vertices, largest error was 0.00000016098469
25 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000005503917
26 Correct 5 ms 376 KB used 108 vertices, largest error was 0.00000004999999
27 Correct 5 ms 376 KB used 196 vertices, largest error was 0.00000011900000
28 Correct 5 ms 376 KB used 220 vertices, largest error was 0.00000080749741
29 Correct 5 ms 376 KB used 132 vertices, largest error was 0.00000017862311
30 Correct 5 ms 376 KB used 84 vertices, largest error was 0.00000122181102
31 Runtime error 85 ms 93048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB used 36 vertices, largest error was 0.00000002800000
2 Correct 5 ms 380 KB used 28 vertices, largest error was 0.00000000800000
3 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000001600000
4 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
5 Correct 5 ms 248 KB used 28 vertices, largest error was 0.00000000800000
6 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
7 Correct 5 ms 376 KB used 28 vertices, largest error was 0.00000000800000
8 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000002500000
9 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000001900000
10 Correct 5 ms 248 KB used 28 vertices, largest error was 0.00000000800000
11 Correct 5 ms 380 KB used 76 vertices, largest error was 0.00000002500000
12 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000000800000
13 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000003400000
14 Correct 5 ms 376 KB used 292 vertices, largest error was 0.00000397399997
15 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000006208642
16 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000008810256
17 Correct 5 ms 376 KB used 84 vertices, largest error was 0.00000009211111
18 Correct 5 ms 376 KB used 420 vertices, largest error was 0.00000658916321
19 Correct 5 ms 376 KB used 44 vertices, largest error was 0.00000003900000
20 Correct 5 ms 376 KB used 132 vertices, largest error was 0.00000005300000
21 Correct 5 ms 376 KB used 140 vertices, largest error was 0.00001206266664
22 Correct 5 ms 248 KB used 124 vertices, largest error was 0.00000020385384
23 Correct 5 ms 376 KB used 172 vertices, largest error was 0.00000018094929
24 Correct 5 ms 376 KB used 220 vertices, largest error was 0.00000016098469
25 Correct 5 ms 376 KB used 100 vertices, largest error was 0.00000005503917
26 Correct 5 ms 376 KB used 108 vertices, largest error was 0.00000004999999
27 Correct 5 ms 376 KB used 196 vertices, largest error was 0.00000011900000
28 Correct 5 ms 376 KB used 220 vertices, largest error was 0.00000080749741
29 Correct 5 ms 376 KB used 132 vertices, largest error was 0.00000017862311
30 Correct 5 ms 376 KB used 84 vertices, largest error was 0.00000122181102
31 Runtime error 85 ms 93048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -