oj.uz

Submission #545934

# Submission time Handle Problem Language Result Execution time Memory
545934 2022-04-05T16:13:29 Z rainboy Scissors and Tape (CEOI19_scissors) C++
100 / 100
 2 ms 316 KB 
/* https://codeforces.com/blog/entry/68748 */
#include <math.h>
#include <stdio.h>

#define N	10

double dot2(double x1, double y1, double x2, double y2) {
	return x1 * x2 + y1 * y2;
}

double cross2(double x1, double y1, double x2, double y2) {
	return x1 * y2 - x2 * y1;
}

double dot(double x0, double y0, double x1, double y1, double x2, double y2) {
	return dot2(x1 - x0, y1 - y0, x2 - x0, y2 - y0);
}

int *xx, *yy;

double cross(int i, int j, int k) {
	return cross2(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]);
}

int m;

int rect2rect(double x1, double y1, double x2, double y2, int h) {
	if (x1 == x2)
		return h;
	if (x1 * 2 <= x2) {
		printf("scissors\n");
		printf("%d 2\n", h);
		printf("4 %d %d %f %d %f %f %d %f\n", 0, 0, x1, 0, x1, y1 / 2, 0, y1 / 2);
		printf("4 %d %f %f %f %f %f %d %f\n", 0, y1 / 2, x1, y1 / 2, x1, y1, 0, y1);
		printf("tape\n");
		printf("2 %d %d\n", m + 1, m + 2);
		printf("4 %d %d %f %d %f %f %d %f\n", 0, 0, x1, 0, x1, y1 / 2, 0, y1 / 2);
		printf("4 %f %d %f %d %f %f %f %f\n", x1, 0, x1 * 2, 0, x1 * 2, y1 / 2, x1, y1 / 2);
		printf("4 %d %d %f %d %f %f %d %f\n", 0, 0, x1 * 2, 0, x1 * 2, y1 / 2, 0, y1 / 2);
		return rect2rect(x1 * 2, y1 / 2, x2, y2, m += 3);
	} else if (x1 / 2 >= x2) {
		printf("scissors\n");
		printf("%d 2\n", h);
		printf("4 %d %d %f %d %f %f %d %f\n", 0, 0, x1 / 2, 0, x1 / 2, y1, 0, y1);
		printf("4 %f %d %f %d %f %f %f %f\n", x1 / 2, 0, x1, 0, x1, y1, x1 / 2, y1);
		printf("tape\n");
		printf("2 %d %d\n", m + 1, m + 2);
		printf("4 %d %d %f %d %f %f %d %f\n", 0, 0, x1 / 2, 0, x1 / 2, y1, 0, y1);
		printf("4 %d %f %f %f %f %f %d %f\n", 0, y1, x1 / 2, y1, x1 / 2, y1 * 2, 0, y1 * 2);
		printf("4 %d %d %f %d %f %f %d %f\n", 0, 0, x1 / 2, 0, x1 / 2, y1 * 2, 0, y1 * 2);
		return rect2rect(x1 / 2, y1 * 2, x2, y2, m += 3);
	} else if (x1 > x2) {
		printf("scissors\n");
		printf("%d 3\n", h);
		printf("5 %d %d %f %d %f %f %f %f %d %f\n", 0, 0, x2, 0, x2, y2 - y1, x1 - x2, y1, 0, y1);
		printf("3 %f %d %f %d %f %f\n", x2, 0, x1, 0, x2, y2 - y1);
		printf("3 %f %d %f %f %f %f\n", x1, 0, x1, y1, x1 - x2, y1);
		printf("tape\n");
		printf("3 %d %d %d\n", m + 1, m + 2, m + 3);
		printf("5 %d %d %f %d %f %f %f %f %d %f\n", 0, 0, x2, 0, x2, y2 - y1, x1 - x2, y1, 0, y1);
		printf("3 %d %f %f %f %d %f\n", 0, y1, x1 - x2, y1, 0, y2);
		printf("3 %f %f %f %f %d %f\n", x2, y2 - y1, x2, y2, 0, y2);
		printf("4 %d %d %f %d %f %f %d %f\n", 0, 0, x2, 0, x2, y2, 0, y2);
		return m += 4;
	} else {
		printf("scissors\n");
		printf("%d 3\n", h);
		printf("5 %d %d %f %d %f %f %f %f %d %f\n", 0, 0, x1, 0, x1, y1 - y2, x2 - x1, y2, 0, y2);
		printf("3 %d %f %f %f %d %f\n", 0, y2, x2 - x1, y2, 0, y1);
		printf("3 %f %f %f %f %d %f\n", x1, y1 - y2, x1, y1, 0, y1);
		printf("tape\n");
		printf("3 %d %d %d\n", m + 1, m + 2, m + 3);
		printf("5 %d %d %f %d %f %f %f %f %d %f\n", 0, 0, x1, 0, x1, y1 - y2, x2 - x1, y2, 0, y2);
		printf("3 %f %d %f %d %f %f\n", x1, 0, x2, 0, x1, y1 - y2);
		printf("3 %f %d %f %f %f %f\n", x2, 0, x2, y2, x2 - x1, y2);
		printf("4 %d %d %f %d %f %f %d %f\n", 0, 0, x2, 0, x2, y2, 0, y2);
		return m += 4;
	}
}

int tri2rect(double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4, int h) {
	double a, b, c;

	if (dot(x0, y0, x1, y1, x2, y2) < 0) {
		printf("tape\n");
		printf("1 %d\n", h);
		printf("3 %f %f %f %f %f %f\n", x0, y0, x1, y1, x2, y2);
		printf("3 %f %f %f %f %f %f\n", x1, y1, x2, y2, x0, y0);
		return tri2rect(x1, y1, x2, y2, x0, y0, x3, y3, x4, y4, ++m);
	}
	if (dot(x1, y1, x0, y0, x2, y2) < 0) {
		printf("tape\n");
		printf("1 %d\n", h);
		printf("3 %f %f %f %f %f %f\n", x0, y0, x1, y1, x2, y2);
		printf("3 %f %f %f %f %f %f\n", x2, y2, x0, y0, x1, y1);
		return tri2rect(x2, y2, x0, y0, x1, y1, x3, y3, x4, y4, ++m);
	}
	if (x0 != 0 || y0 != 0 || x1 <= x0 || y1 != y0) {
		double d = hypot(x1 - x0, y1 - y0), x1_ = (x1 - x0) / d, y1_ = (y1 - y0) / d;
		double x2_ = (x2 - x0) * x1_ + (y2 - y0) * y1_, y2_ = (y2 - y0) * x1_ - (x2 - x0) * y1_;

		printf("tape\n");
		printf("1 %d\n", h);
		printf("3 %d %d %f %d %f %f\n", 0, 0, d, 0, x2_, y2_);
		printf("3 %d %d %f %d %f %f\n", 0, 0, d, 0, x2_, y2_);
		return tri2rect(0, 0, d, 0, x2_, y2_, x3, y3, x4, y4, ++m);
	}
	printf("scissors\n");
	printf("%d 2\n", h);
	printf("4 %d %d %f %d %f %f %f %f\n", 0, 0, x1, 0, (x2 + x1) / 2, y2 / 2, x2 / 2, y2 / 2);
	printf("3 %f %f %f %f %f %f\n", x2 / 2, y2 / 2, (x2 + x1) / 2, y2 / 2, x2, y2);
	printf("tape\n");
	printf("2 %d %d\n", m + 1, m + 2);
	printf("4 %d %d %f %d %f %f %f %f\n", 0, 0, x1, 0, (x2 + x1) / 2, y2 / 2, x2 / 2, y2 / 2);
	printf("3 %f %f %f %f %f %d\n", x2 / 2 + x1, y2 / 2, (x2 + x1) / 2, y2 / 2, x1, 0);
	printf("4 %d %d %f %d %f %f %f %f\n", 0, 0, x1, 0, x2 / 2 + x1, y2 / 2, x2 / 2, y2 / 2);
	h = m += 3;
	a = x1, b = x2 / 2, c = y2 / 2;
	if (b != 0) {
		printf("scissors\n");
		printf("%d 2\n", h);
		printf("4 %d %d %f %d %f %f %f %f\n", 0, 0, a, 0, a, c, b, c);
		printf("3 %f %d %f %f %f %f\n", a, 0, a + b, c, a, c);
		printf("tape\n");
		printf("2 %d %d\n", m + 1, m + 2);
		printf("4 %d %d %f %d %f %f %f %f\n", 0, 0, a, 0, a, c, b, c);
		printf("3 %d %d %f %f %d %f\n", 0, 0, b, c, 0, c);
		printf("4 %d %d %f %d %f %f %d %f\n", 0, 0, a, 0, a, c, 0, c);
		h = m += 3;
	}
	h = rect2rect(a, c, x4 - x3, y4 - y3, h);
	if (x3 != 0 || y3 != 0) {
		printf("tape\n");
		printf("1 %d\n", h);
		printf("4 %f %f %f %f %f %f %f %f\n", x3, y3, x4, y3, x4, y4, x3, y4);
		printf("4 %f %f %f %f %f %f %f %f\n", x3, y3, x4, y3, x4, y4, x3, y4);
		h = ++m;
	}
	return h;
}

int rect2tri(double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4, int h) {
	double a, b, c;

	if (dot(x0, y0, x1, y1, x2, y2) < 0) {
		h = rect2tri(x1, y1, x2, y2, x0, y0, x3, y3, x4, y4, h);
		printf("tape\n");
		printf("1 %d\n", h);
		printf("3 %f %f %f %f %f %f\n", x1, y1, x2, y2, x0, y0);
		printf("3 %f %f %f %f %f %f\n", x0, y0, x1, y1, x2, y2);
		return ++m;
	}
	if (dot(x1, y1, x0, y0, x2, y2) < 0) {
		h = rect2tri(x2, y2, x0, y0, x1, y1, x3, y3, x4, y4, h);
		printf("tape\n");
		printf("1 %d\n", h);
		printf("3 %f %f %f %f %f %f\n", x2, y2, x0, y0, x1, y1);
		printf("3 %f %f %f %f %f %f\n", x0, y0, x1, y1, x2, y2);
		return ++m;
	}
	if (x0 != 0 || y0 != 0 || x1 <= x0 || y1 != y0) {
		double d = hypot(x1 - x0, y1 - y0), x1_ = (x1 - x0) / d, y1_ = (y1 - y0) / d;
		double x2_ = (x2 - x0) * x1_ + (y2 - y0) * y1_, y2_ = (y2 - y0) * x1_ - (x2 - x0) * y1_;

		h = rect2tri(0, 0, d, 0, x2_, y2_, x3, y3, x4, y4, h);
		printf("tape\n");
		printf("1 %d\n", h);
		printf("3 %f %f %f %f %f %f\n", x0, y0, x1, y1, x2, y2);
		printf("3 %f %f %f %f %f %f\n", x0, y0, x1, y1, x2, y2);
		return ++m;
	}
	a = x1, b = x2 / 2, c = y2 / 2;
	if (x3 != 0 || y3 != 0) {
		x4 -= x3, y4 -= y3, x3 = 0, y3 = 0;
		printf("tape\n");
		printf("1 %d\n", h);
		printf("4 %f %f %f %f %f %f %f %f\n", x3, y3, x4, y3, x4, y4, x3, y4);
		printf("4 %f %f %f %f %f %f %f %f\n", x3, y3, x4, y3, x4, y4, x3, y4);
		h = ++m;
	}
	h = rect2rect(x4, y4, a, c, h);
	if (b != 0) {
		printf("scissors\n");
		printf("%d 2\n", h);
		printf("4 %d %d %f %d %f %f %f %f\n", 0, 0, a, 0, a, c, b, c);
		printf("3 %d %d %f %f %d %f\n", 0, 0, b, c, 0, c);
		printf("tape\n");
		printf("2 %d %d\n", m + 1, m + 2);
		printf("4 %d %d %f %d %f %f %f %f\n", 0, 0, a, 0, a, c, b, c);
		printf("3 %f %d %f %f %f %f\n", a, 0, a + b, c, a, c);
		printf("4 %d %d %f %d %f %f %f %f\n", 0, 0, a, 0, a + b, c, b, c);
		h = m += 3;
	}
	printf("scissors\n");
	printf("%d 2\n", h);
	printf("4 %d %d %f %d %f %f %f %f\n", 0, 0, x1, 0, (x2 + x1) / 2, y2 / 2, x2 / 2, y2 / 2);
	printf("3 %f %f %f %f %f %d\n", x2 / 2 + x1, y2 / 2, (x2 + x1) / 2, y2 / 2, x1, 0);
	printf("tape\n");
	printf("2 %d %d\n", m + 1, m + 2);
	printf("4 %d %d %f %d %f %f %f %f\n", 0, 0, x1, 0, (x2 + x1) / 2, y2 / 2, x2 / 2, y2 / 2);
	printf("3 %f %f %f %f %f %f\n", x2 / 2, y2 / 2, (x2 + x1) / 2, y2 / 2, x2, y2);
	printf("3 %f %f %f %f %f %f\n", x0, y0, x1, y1, x2, y2);
	h = m += 3;
	return h;
}

int ii_[N], n_;

int inside(int i, int j) {
	int p = (i - 1 + n_) % n_, q = (i + 1 + n_) % n_;
	double cpq = cross(ii_[i], ii_[p], ii_[q]);
	double cpj = cross(ii_[i], ii_[p], ii_[j]);
	double cjq = cross(ii_[i], ii_[j], ii_[q]);

	return cpq < 0 ? cpj < 0 && cjq < 0 : cpj < 0 || cjq < 0;
}

int check(int i, int j) {
	int k, l;

	if (!inside(i, j))
		return 0;
	for (k = 0; k < n_; k++) {
		l = (k + 1) % n_;
		if (k == i || k == j || l == i || l == j)
			continue;
		if ((cross(ii_[i], ii_[j], ii_[k]) < 0) != (cross(ii_[i], ii_[j], ii_[l]) < 0)
				&& (cross(ii_[k], ii_[l], ii_[i]) < 0) != (cross(ii_[k], ii_[l], ii_[j]) < 0))
			return 0;
	}
	return 1;
}

int ii[N], jj[N], kk[N];

void triangulate(int n, int b) {
	int h, i, j, b1, b2;

	n_ = 0;
	for (i = 0; i < n; i++)
		if ((b & 1 << i) != 0)
			ii_[n_++] = i;
	if (n_ == 3) {
		m++, ii[m] = ii_[0], jj[m] = ii_[1], kk[m] = ii_[2];
		return;
	}
	for (i = 0; i < n_; i++)
		for (j = i + 1; j < n_; j++)
			if (check(i, j)) {
				b1 = b2 = 1 << ii_[j];
				for (h = i; h != j; h = (h + 1) % n_)
					b1 |= 1 << ii_[h];
				for (h = i; h != j; h = (h - 1 + n_) % n_)
					b2 |= 1 << ii_[h];
				triangulate(n, b1), triangulate(n, b2);
				return;
			}
}

int main() {
	static int xx1[N], yy1[N], xx2[N], yy2[N], hh[N];
	static double yy_[N];
	int n1, n2, m_, g, i, j, k;
	double s;

	scanf("%d", &n1);
	for (i = 0; i < n1; i++)
		scanf("%d%d", &xx1[i], &yy1[i]);
	scanf("%d", &n2);
	for (j = 0; j < n2; j++)
		scanf("%d%d", &xx2[j], &yy2[j]);
	s = 0;
	for (i = 0; i < n1; i++)
		s += cross2(xx1[i], yy1[i], xx1[(i + 1) % n1], yy1[(i + 1) % n1]);
	s = sqrt(s / 2);
	xx = xx1, yy = yy1;
	m = 0, triangulate(n1, (1 << n1) - 1);
	printf("scissors\n");
	printf("0 %d\n", n1 - 2);
	for (g = 1; g < n1 - 1; g++) {
		i = ii[g], j = jj[g], k = kk[g];
		printf("3 %d %d %d %d %d %d\n", xx1[i], yy1[i], xx1[j], yy1[j], xx1[k], yy1[k]);
	}
	for (g = 1; g < n1 - 1; g++) {
		i = ii[g], j = jj[g], k = kk[g];
		yy_[g] = yy_[g - 1] + cross(i, j, k) / 2 / s;
		hh[g] = tri2rect(xx1[i], yy1[i], xx1[j], yy1[j], xx1[k], yy1[k], 0, yy_[g - 1], s, yy_[g], g);
	}
	printf("tape\n");
	printf("%d", n1 - 2);
	for (g = 1; g < n1 - 1; g++)
		printf(" %d", hh[g]);
	printf("\n");
	for (g = 1; g < n1 - 1; g++)
		printf("4 %d %f %f %f %f %f %d %f\n", 0, yy_[g - 1], s, yy_[g - 1], s, yy_[g], 0, yy_[g]);
	printf("4 %d %d %f %d %f %f %d %f\n", 0, 0, s, 0, s, s, 0, s);
	m++;
	xx = xx2, yy = yy2;
	m_ = m, m = 0, triangulate(n2, (1 << n2) - 1);
	for (g = 1; g < n2 - 1; g++) {
		i = ii[g], j = jj[g], k = kk[g];
		yy_[g] = yy_[g - 1] + cross(i, j, k) / 2 / s;
	}
	printf("scissors\n");
	printf("%d %d\n", m_, n2 - 2);
	for (g = 1; g < n2 - 1; g++) {
		i = ii[g], j = jj[g], k = kk[g];
		printf("4 %d %f %f %f %f %f %d %f\n", 0, yy_[g - 1], s, yy_[g - 1], s, yy_[g], 0, yy_[g]);
	}
	m += m_;
	for (g = 1; g < n2 - 1; g++) {
		i = ii[g], j = jj[g], k = kk[g];
		hh[g] = rect2tri(xx2[i], yy2[i], xx2[j], yy2[j], xx2[k], yy2[k], 0, yy_[g - 1], s, yy_[g], m_ + g);
	}
	printf("tape\n");
	printf("%d", n2 - 2);
	for (g = 1; g < n2 - 1; g++)
		printf(" %d", hh[g]);
	printf("\n");
	for (g = 1; g < n2 - 1; g++) {
		i = ii[g], j = jj[g], k = kk[g];
		printf("3 %d %d %d %d %d %d\n", xx2[i], yy2[i], xx2[j], yy2[j], xx2[k], yy2[k]);
	}
	printf("%d", n2);
	for (j = 0; j < n2; j++)
		printf(" %d %d", xx2[j], yy2[j]);
	printf("\n");
	m++;
	return 0;
}

Compilation message

scissors.cpp: In function 'int main()':
scissors.cpp:266:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  266 |  scanf("%d", &n1);
      |  ~~~~~^~~~~~~~~~~
scissors.cpp:268:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  268 |   scanf("%d%d", &xx1[i], &yy1[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
scissors.cpp:269:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  269 |  scanf("%d", &n2);
      |  ~~~~~^~~~~~~~~~~
scissors.cpp:271:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  271 |   scanf("%d%d", &xx2[j], &yy2[j]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB used 318 vertices, largest error was 0.00000069337502
2 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000237206214
3 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000169069490
4 Correct 1 ms 212 KB used 306 vertices, largest error was 0.00000415775695
5 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000237206214
6 Correct 1 ms 284 KB used 358 vertices, largest error was 0.00000237206214
7 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000238808858
8 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000171248941
9 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000169069490
10 Correct 1 ms 212 KB used 306 vertices, largest error was 0.00001293682705

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000011085760
2 Correct 1 ms 212 KB used 346 vertices, largest error was 0.00000410199578
3 Correct 1 ms 212 KB used 332 vertices, largest error was 0.00000077200226
4 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000206199551
5 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000004693343
6 Correct 1 ms 276 KB used 292 vertices, largest error was 0.00000017867602
7 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000004078592
8 Correct 1 ms 284 KB used 292 vertices, largest error was 0.00000008832280
9 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000008700000
10 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000015108160

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB used 318 vertices, largest error was 0.00000069337502
2 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000237206214
3 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000169069490
4 Correct 1 ms 212 KB used 306 vertices, largest error was 0.00000415775695
5 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000237206214
6 Correct 1 ms 284 KB used 358 vertices, largest error was 0.00000237206214
7 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000238808858
8 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000171248941
9 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000169069490
10 Correct 1 ms 212 KB used 306 vertices, largest error was 0.00001293682705
11 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000011085760
12 Correct 1 ms 212 KB used 346 vertices, largest error was 0.00000410199578
13 Correct 1 ms 212 KB used 332 vertices, largest error was 0.00000077200226
14 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000206199551
15 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000004693343
16 Correct 1 ms 276 KB used 292 vertices, largest error was 0.00000017867602
17 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000004078592
18 Correct 1 ms 284 KB used 292 vertices, largest error was 0.00000008832280
19 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000008700000
20 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000015108160
21 Correct 1 ms 212 KB used 398 vertices, largest error was 0.00000145627262
22 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000016659123
23 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000003403290
24 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000073388743
25 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000004026402
26 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000003200000
27 Correct 1 ms 220 KB used 318 vertices, largest error was 0.00000006651239
28 Correct 1 ms 280 KB used 318 vertices, largest error was 0.00000003200000
29 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000012083399
30 Correct 1 ms 280 KB used 358 vertices, largest error was 0.00000003200000

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000002200000
2 Correct 1 ms 212 KB used 214 vertices, largest error was 0.00000004200000
3 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000011605371
4 Correct 1 ms 280 KB used 240 vertices, largest error was 0.00000004371966
5 Correct 1 ms 284 KB used 234 vertices, largest error was 0.00000013584144
6 Correct 1 ms 212 KB used 234 vertices, largest error was 0.00000003390678
7 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000048360280
8 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000008637088
9 Correct 1 ms 212 KB used 260 vertices, largest error was 0.00000004298278
10 Correct 1 ms 212 KB used 234 vertices, largest error was 0.00000002600000

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 182 vertices, largest error was 0.00000005427392
2 Correct 1 ms 212 KB used 208 vertices, largest error was 0.00000002667525
3 Correct 1 ms 212 KB used 208 vertices, largest error was 0.00000003966555
4 Correct 1 ms 212 KB used 234 vertices, largest error was 0.00000003186011
5 Correct 1 ms 212 KB used 254 vertices, largest error was 0.00000003454953
6 Correct 1 ms 280 KB used 208 vertices, largest error was 0.00000030951033
7 Correct 1 ms 212 KB used 254 vertices, largest error was 0.00000008449363
8 Correct 1 ms 212 KB used 228 vertices, largest error was 0.00000002550742
9 Correct 1 ms 212 KB used 208 vertices, largest error was 0.00000002491753
10 Correct 1 ms 280 KB used 208 vertices, largest error was 0.00000003342856

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB used 318 vertices, largest error was 0.00000069337502
2 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000237206214
3 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000169069490
4 Correct 1 ms 212 KB used 306 vertices, largest error was 0.00000415775695
5 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000237206214
6 Correct 1 ms 284 KB used 358 vertices, largest error was 0.00000237206214
7 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000238808858
8 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000171248941
9 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000169069490
10 Correct 1 ms 212 KB used 306 vertices, largest error was 0.00001293682705
11 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000011085760
12 Correct 1 ms 212 KB used 346 vertices, largest error was 0.00000410199578
13 Correct 1 ms 212 KB used 332 vertices, largest error was 0.00000077200226
14 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000206199551
15 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000004693343
16 Correct 1 ms 276 KB used 292 vertices, largest error was 0.00000017867602
17 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000004078592
18 Correct 1 ms 284 KB used 292 vertices, largest error was 0.00000008832280
19 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000008700000
20 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000015108160
21 Correct 1 ms 212 KB used 398 vertices, largest error was 0.00000145627262
22 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000016659123
23 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000003403290
24 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000073388743
25 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000004026402
26 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000003200000
27 Correct 1 ms 220 KB used 318 vertices, largest error was 0.00000006651239
28 Correct 1 ms 280 KB used 318 vertices, largest error was 0.00000003200000
29 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000012083399
30 Correct 1 ms 280 KB used 358 vertices, largest error was 0.00000003200000
31 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000002200000
32 Correct 1 ms 212 KB used 214 vertices, largest error was 0.00000004200000
33 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000011605371
34 Correct 1 ms 280 KB used 240 vertices, largest error was 0.00000004371966
35 Correct 1 ms 284 KB used 234 vertices, largest error was 0.00000013584144
36 Correct 1 ms 212 KB used 234 vertices, largest error was 0.00000003390678
37 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000048360280
38 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000008637088
39 Correct 1 ms 212 KB used 260 vertices, largest error was 0.00000004298278
40 Correct 1 ms 212 KB used 234 vertices, largest error was 0.00000002600000
41 Correct 1 ms 212 KB used 594 vertices, largest error was 0.00000030741936
42 Correct 1 ms 212 KB used 420 vertices, largest error was 0.00000018783696
43 Correct 1 ms 212 KB used 762 vertices, largest error was 0.00000018269154
44 Correct 1 ms 288 KB used 582 vertices, largest error was 0.00000010971797
45 Correct 1 ms 284 KB used 498 vertices, largest error was 0.00000003730085
46 Correct 1 ms 280 KB used 420 vertices, largest error was 0.00000005947076
47 Correct 1 ms 212 KB used 414 vertices, largest error was 0.00000003772442
48 Correct 1 ms 280 KB used 420 vertices, largest error was 0.00000003108232
49 Correct 1 ms 212 KB used 420 vertices, largest error was 0.00000009576618
50 Correct 1 ms 212 KB used 588 vertices, largest error was 0.00000029691732

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB used 318 vertices, largest error was 0.00000069337502
2 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000237206214
3 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000169069490
4 Correct 1 ms 212 KB used 306 vertices, largest error was 0.00000415775695
5 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000237206214
6 Correct 1 ms 284 KB used 358 vertices, largest error was 0.00000237206214
7 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000238808858
8 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000171248941
9 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000169069490
10 Correct 1 ms 212 KB used 306 vertices, largest error was 0.00001293682705
11 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000011085760
12 Correct 1 ms 212 KB used 346 vertices, largest error was 0.00000410199578
13 Correct 1 ms 212 KB used 332 vertices, largest error was 0.00000077200226
14 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000206199551
15 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000004693343
16 Correct 1 ms 276 KB used 292 vertices, largest error was 0.00000017867602
17 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000004078592
18 Correct 1 ms 284 KB used 292 vertices, largest error was 0.00000008832280
19 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000008700000
20 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000015108160
21 Correct 1 ms 212 KB used 398 vertices, largest error was 0.00000145627262
22 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000016659123
23 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000003403290
24 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000073388743
25 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000004026402
26 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000003200000
27 Correct 1 ms 220 KB used 318 vertices, largest error was 0.00000006651239
28 Correct 1 ms 280 KB used 318 vertices, largest error was 0.00000003200000
29 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000012083399
30 Correct 1 ms 280 KB used 358 vertices, largest error was 0.00000003200000
31 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000002200000
32 Correct 1 ms 212 KB used 214 vertices, largest error was 0.00000004200000
33 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000011605371
34 Correct 1 ms 280 KB used 240 vertices, largest error was 0.00000004371966
35 Correct 1 ms 284 KB used 234 vertices, largest error was 0.00000013584144
36 Correct 1 ms 212 KB used 234 vertices, largest error was 0.00000003390678
37 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000048360280
38 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000008637088
39 Correct 1 ms 212 KB used 260 vertices, largest error was 0.00000004298278
40 Correct 1 ms 212 KB used 234 vertices, largest error was 0.00000002600000
41 Correct 1 ms 212 KB used 594 vertices, largest error was 0.00000030741936
42 Correct 1 ms 212 KB used 420 vertices, largest error was 0.00000018783696
43 Correct 1 ms 212 KB used 762 vertices, largest error was 0.00000018269154
44 Correct 1 ms 288 KB used 582 vertices, largest error was 0.00000010971797
45 Correct 1 ms 284 KB used 498 vertices, largest error was 0.00000003730085
46 Correct 1 ms 280 KB used 420 vertices, largest error was 0.00000005947076
47 Correct 1 ms 212 KB used 414 vertices, largest error was 0.00000003772442
48 Correct 1 ms 280 KB used 420 vertices, largest error was 0.00000003108232
49 Correct 1 ms 212 KB used 420 vertices, largest error was 0.00000009576618
50 Correct 1 ms 212 KB used 588 vertices, largest error was 0.00000029691732
51 Correct 1 ms 212 KB used 852 vertices, largest error was 0.00000007130676
52 Correct 2 ms 316 KB used 828 vertices, largest error was 0.00000043997526
53 Correct 1 ms 212 KB used 596 vertices, largest error was 0.00000006331671
54 Correct 1 ms 212 KB used 674 vertices, largest error was 0.00000027574135
55 Correct 1 ms 212 KB used 712 vertices, largest error was 0.00000026734631
56 Correct 1 ms 212 KB used 886 vertices, largest error was 0.00000006051411
57 Correct 1 ms 212 KB used 810 vertices, largest error was 0.00000006486482
58 Correct 1 ms 212 KB used 920 vertices, largest error was 0.00000011576750
59 Correct 1 ms 212 KB used 764 vertices, largest error was 0.00000021300408
60 Correct 1 ms 212 KB used 870 vertices, largest error was 0.00000006689829

Subtask #8
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 276 KB used 318 vertices, largest error was 0.00000069337502
2 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000237206214
3 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000169069490
4 Correct 1 ms 212 KB used 306 vertices, largest error was 0.00000415775695
5 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000237206214
6 Correct 1 ms 284 KB used 358 vertices, largest error was 0.00000237206214
7 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000238808858
8 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000171248941
9 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000169069490
10 Correct 1 ms 212 KB used 306 vertices, largest error was 0.00001293682705
11 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000011085760
12 Correct 1 ms 212 KB used 346 vertices, largest error was 0.00000410199578
13 Correct 1 ms 212 KB used 332 vertices, largest error was 0.00000077200226
14 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000206199551
15 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000004693343
16 Correct 1 ms 276 KB used 292 vertices, largest error was 0.00000017867602
17 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000004078592
18 Correct 1 ms 284 KB used 292 vertices, largest error was 0.00000008832280
19 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000008700000
20 Correct 1 ms 212 KB used 292 vertices, largest error was 0.00000015108160
21 Correct 1 ms 212 KB used 398 vertices, largest error was 0.00000145627262
22 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000016659123
23 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000003403290
24 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000073388743
25 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000004026402
26 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000003200000
27 Correct 1 ms 220 KB used 318 vertices, largest error was 0.00000006651239
28 Correct 1 ms 280 KB used 318 vertices, largest error was 0.00000003200000
29 Correct 1 ms 212 KB used 358 vertices, largest error was 0.00000012083399
30 Correct 1 ms 280 KB used 358 vertices, largest error was 0.00000003200000
31 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000002200000
32 Correct 1 ms 212 KB used 214 vertices, largest error was 0.00000004200000
33 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000011605371
34 Correct 1 ms 280 KB used 240 vertices, largest error was 0.00000004371966
35 Correct 1 ms 284 KB used 234 vertices, largest error was 0.00000013584144
36 Correct 1 ms 212 KB used 234 vertices, largest error was 0.00000003390678
37 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000048360280
38 Correct 1 ms 212 KB used 240 vertices, largest error was 0.00000008637088
39 Correct 1 ms 212 KB used 260 vertices, largest error was 0.00000004298278
40 Correct 1 ms 212 KB used 234 vertices, largest error was 0.00000002600000
41 Correct 1 ms 212 KB used 182 vertices, largest error was 0.00000005427392
42 Correct 1 ms 212 KB used 208 vertices, largest error was 0.00000002667525
43 Correct 1 ms 212 KB used 208 vertices, largest error was 0.00000003966555
44 Correct 1 ms 212 KB used 234 vertices, largest error was 0.00000003186011
45 Correct 1 ms 212 KB used 254 vertices, largest error was 0.00000003454953
46 Correct 1 ms 280 KB used 208 vertices, largest error was 0.00000030951033
47 Correct 1 ms 212 KB used 254 vertices, largest error was 0.00000008449363
48 Correct 1 ms 212 KB used 228 vertices, largest error was 0.00000002550742
49 Correct 1 ms 212 KB used 208 vertices, largest error was 0.00000002491753
50 Correct 1 ms 280 KB used 208 vertices, largest error was 0.00000003342856
51 Correct 1 ms 212 KB used 594 vertices, largest error was 0.00000030741936
52 Correct 1 ms 212 KB used 420 vertices, largest error was 0.00000018783696
53 Correct 1 ms 212 KB used 762 vertices, largest error was 0.00000018269154
54 Correct 1 ms 288 KB used 582 vertices, largest error was 0.00000010971797
55 Correct 1 ms 284 KB used 498 vertices, largest error was 0.00000003730085
56 Correct 1 ms 280 KB used 420 vertices, largest error was 0.00000005947076
57 Correct 1 ms 212 KB used 414 vertices, largest error was 0.00000003772442
58 Correct 1 ms 280 KB used 420 vertices, largest error was 0.00000003108232
59 Correct 1 ms 212 KB used 420 vertices, largest error was 0.00000009576618
60 Correct 1 ms 212 KB used 588 vertices, largest error was 0.00000029691732
61 Correct 1 ms 212 KB used 852 vertices, largest error was 0.00000007130676
62 Correct 2 ms 316 KB used 828 vertices, largest error was 0.00000043997526
63 Correct 1 ms 212 KB used 596 vertices, largest error was 0.00000006331671
64 Correct 1 ms 212 KB used 674 vertices, largest error was 0.00000027574135
65 Correct 1 ms 212 KB used 712 vertices, largest error was 0.00000026734631
66 Correct 1 ms 212 KB used 886 vertices, largest error was 0.00000006051411
67 Correct 1 ms 212 KB used 810 vertices, largest error was 0.00000006486482
68 Correct 1 ms 212 KB used 920 vertices, largest error was 0.00000011576750
69 Correct 1 ms 212 KB used 764 vertices, largest error was 0.00000021300408
70 Correct 1 ms 212 KB used 870 vertices, largest error was 0.00000006689829
71 Correct 2 ms 284 KB used 1362 vertices, largest error was 0.00000024188446
72 Correct 1 ms 284 KB used 1162 vertices, largest error was 0.00000024167937
73 Correct 2 ms 212 KB used 1374 vertices, largest error was 0.00000011265425
74 Correct 2 ms 212 KB used 1150 vertices, largest error was 0.00000191817028
75 Correct 2 ms 212 KB used 1208 vertices, largest error was 0.00000021065897
76 Correct 2 ms 280 KB used 1246 vertices, largest error was 0.00000016938564
77 Correct 2 ms 284 KB used 1170 vertices, largest error was 0.00000065043604
78 Correct 2 ms 284 KB used 1420 vertices, largest error was 0.00003134546757
79 Correct 2 ms 212 KB used 1406 vertices, largest error was 0.00000037955381