/* 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.c: In function 'main':
scissors.c:266:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
266 | scanf("%d", &n1);
| ^~~~~~~~~~~~~~~~
scissors.c:268:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
268 | scanf("%d%d", &xx1[i], &yy1[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scissors.c:269:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
269 | scanf("%d", &n2);
| ^~~~~~~~~~~~~~~~
scissors.c:271:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
271 | scanf("%d%d", &xx2[j], &yy2[j]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccl0Z8Yq.o: in function `tri2rect':
scissors.c:(.text+0xcef): undefined reference to `hypot'
/usr/bin/ld: /tmp/ccl0Z8Yq.o: in function `rect2tri':
scissors.c:(.text+0x1c32): undefined reference to `hypot'
/usr/bin/ld: /tmp/ccl0Z8Yq.o: in function `main':
scissors.c:(.text.startup+0x849): undefined reference to `sqrt'
collect2: error: ld returned 1 exit status
