Submission #545934

#	Time	Username	Problem	Language	Result	Execution time	Memory
545934		rainboy	Scissors and Tape (CEOI19_scissors)	C++98	100 / 100	2 ms	316 KiB

scissors

/* 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 (stderr)

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 / 5
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 10 / 10
• Subtask 6: 16 / 16
• Subtask 7: 11 / 11
• Subtask 8: 19 / 19