제출 #677819

#제출 시각아이디문제언어결과실행 시간메모리
677819JoshcScissors and Tape (CEOI19_scissors)C++11
27 / 100
1 ms300 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pii pair<int, int> #define f first #define s second typedef long double T; typedef complex<T> pt; #define x real() #define y imag() T dot(pt v, pt w) {return (conj(v)*w).x;} T cross(pt v, pt w) {return (conj(v)*w).y;} T orient(pt a, pt b, pt c) {return cross(b-a,c-a);} // positive for left, negative for right, 0 for straight bool half(pt p) {return p.y > 0 || (p.y == 0 && p.x < 0);} // Warning: polarSort shouldn't contain origin void polarSort(vector<pt> &v) {sort(v.begin(), v.end(), [](pt v, pt w) {return make_tuple(half(v), 0) < make_tuple(half(w), cross(v,w));});} bool inDisk(pt a, pt b, pt p) {return dot(a-p, b-p) <= 0;} bool onSegment(pt a, pt b, pt p) {return orient(a,b,p) == 0 && inDisk(a,b,p);} bool intersect(pt a, pt b, pt c, pt d) { if (a == c || a == d || b == c || b == d) return false; if (onSegment(a, b, c)) return true; if (onSegment(a, b, d)) return true; if (onSegment(c, d, a)) return true; if (onSegment(c, d, b)) return true; T oa = orient(c, d, a), ob = orient(c, d, b), oc = orient(a, b, c), od = orient(a, b, d); return ((oa > 0 && ob < 0) || (oa < 0 && ob > 0)) && ((oc > 0 && od < 0) || (oc < 0 && od > 0)); } T area(vector<pt> polygon) { int n = polygon.size(); T res = 0; for (int i=0; i<n; i++) res += polygon[i].x * polygon[(i+1)%n].y - polygon[i].y * polygon[(i+1)%n].x; return abs(res) / 2; } int contains(vector<pt> polygon, pt p) { // Return 0 if outside, 1 if inside, 2 if on boundary int n = polygon.size(), res = 0; for (int i=0; i<n; i++) { if (onSegment(polygon[i], polygon[(i+1)%n], p)) return 2; res ^= ((p.y>=polygon[(i+1)%n].y)-(p.y>=polygon[i].y)) * orient(p, polygon[i], polygon[(i+1)%n]) > 0; } return res; } vector<vector<pt>> shapes; void output(vector<pt> polygon) { printf("%d", polygon.size()); for (pt p : polygon) printf(" %.12Lf %.12Lf", p.x, p.y); printf("\n"); } vector<int> scissors(int original, vector<vector<pt>> pieces) { printf("scissors\n%d %d\n", original, pieces.size()); vector<int> res; for (vector<pt>& piece : pieces) { res.push_back(shapes.size()); shapes.push_back(piece); output(piece); } return res; } int tape(vector<int> pieces, vector<pt> combined) { printf("tape\n%d", pieces.size()); for (int i : pieces) printf(" %d", i); printf("\n"); for (int i : pieces) output(shapes[i]); output(combined); shapes.push_back(combined); return shapes.size()-1; } int move(int shape, vector<pt> loc, int rotatenum = 0) { printf("tape\n1 %d\n", shape); vector<pt> pts; for (int i=rotatenum; i<loc.size(); i++) pts.push_back(loc[i]); for (int i=0; i<rotatenum; i++) pts.push_back(loc[i]); output(pts); output(loc); shapes.push_back(loc); return shapes.size()-1; } vector<pt> read() { int n, a, b; scanf("%d", &n); vector<pt> polygon; for (int i=0; i<n; i++) { scanf("%d%d", &a, &b); polygon.emplace_back(a, b); } return polygon; } vector<pt> genrect(T lx, T rx, T ly, T ry) { return {{lx, ly}, {rx, ly}, {rx, ry}, {lx, ry}}; } int resize(int rectangle, T newwidth) { T newheight = area(shapes[rectangle]) / newwidth; T curwidth = shapes[rectangle][1].x, curheight = shapes[rectangle][2].y; if (abs(newwidth-curwidth) <= 1e-11) return rectangle; if (newwidth > newheight + 1e-11) { int res = resize(rectangle, newheight); return move(res, genrect(0, newwidth, 0, newheight), 1); } if (curheight >= 2 * newheight) { vector<int> halves = scissors(rectangle, {genrect(0, curwidth, 0, curheight/2), genrect(0, curwidth, curheight/2, curheight)}); int h2 = move(halves[1], genrect(curwidth, curwidth*2, 0, curheight/2)); int res = tape({halves[0], h2}, genrect(0, 2*curwidth, 0, curheight/2)); return resize(res, newwidth); } if (curwidth >= 2 * newwidth) { vector<int> halves = scissors(rectangle, {genrect(0, curwidth/2, 0, curheight), genrect(curwidth/2, curwidth, 0, curheight)}); int h2 = move(halves[1], genrect(0, curwidth/2, curheight, curheight*2)); int res = tape({halves[0], h2}, genrect(0, curwidth/2, 0, curheight*2)); return resize(res, newwidth); } if (curwidth < newwidth) { int res = move(rectangle, genrect(0, curheight, 0, curwidth), 1); return resize(res, newwidth); } vector<int> pieces = scissors(rectangle, { {{0, 0}, {newwidth, 0}, {newwidth, newheight-curheight}, {curwidth-newwidth, curheight}, {0, curheight}}, {{newwidth, 0}, {curwidth, 0}, {newwidth, newheight-curheight}}, {{curwidth, 0}, {curwidth, curheight}, {curwidth-newwidth, curheight}} }); int a = pieces[0]; int b2 = move(pieces[1], {{0, curheight}, {curwidth-newwidth, curheight}, {0, newheight}}); int c2 = move(pieces[2], {{newwidth, newheight-curheight}, {newwidth, newheight}, {0, newheight}}); return tape({a, b2, c2}, genrect(0, newwidth, 0, newheight)); } pt calc(vector<pt> triangle) { // If point 0 is at (0, 0) and point 1 is on the positive x axis, where is point 2? // dot(p2-p1, p3-p1) = dot(answer, new p1) T x2 = dot(triangle[2]-triangle[0], (triangle[1]-triangle[0])/abs(triangle[1]-triangle[0])); T y2 = sqrt(dot(triangle[2]-triangle[0], triangle[2]-triangle[0]) - x2 * x2); return pt{x2, y2}; } int rotate(int triangle) { // Make longest side between the first two points T a = abs(shapes[triangle][0] - shapes[triangle][1]), b = abs(shapes[triangle][1] - shapes[triangle][2]), c = abs(shapes[triangle][0] - shapes[triangle][2]); if (a >= b && a >= c) return triangle; if (b >= a && b >= c) return move(triangle, {shapes[triangle][1], shapes[triangle][2], shapes[triangle][0]}, 2); return move(triangle, {shapes[triangle][2], shapes[triangle][0], shapes[triangle][1]}, 1); } int tritorect(int triangle, int newwidth) { triangle = rotate(triangle); pt top = calc(shapes[triangle]); triangle = move(triangle, {{0, 0}, {abs(shapes[triangle][0]-shapes[triangle][1]), 0}, top}); pt a = {top.x/2, top.y/2}, b = {(top.x+shapes[triangle][1].x)/2, top.y/2}, c = {top.x, top.y/2}; vector<int> pieces = scissors(triangle, { {{0, 0}, {shapes[triangle][1].x, 0}, b, a}, {a, c, top}, {c, b, top} }); int A = pieces[0]; int B = move(pieces[1], {a, {0, top.y/2}, {0, 0}}); int C = move(pieces[2], {{shapes[triangle][1].x, top.y/2}, b, {shapes[triangle][1].x, 0}}); int rect = tape({A, B, C}, genrect(0, shapes[triangle][1].x, 0, top.y/2)); return resize(rect, newwidth); } int recttotri(int rectangle, vector<pt> triangle) { T a = abs(triangle[0] - triangle[1]), b = abs(triangle[1] - triangle[2]), c = abs(triangle[0] - triangle[2]); if (b > a && b > c) return move(recttotri(rectangle, {triangle[1], triangle[2], triangle[0]}), triangle, 1); if (c > a && c > b) return move(recttotri(rectangle, {triangle[2], triangle[0], triangle[1]}), triangle, 2); pt top = calc(triangle); rectangle = resize(rectangle, a); pt A = {top.x/2, top.y/2}, B = {(top.x+a)/2, top.y/2}, C = {top.x, top.y/2}; vector<int> pieces = scissors(rectangle, { {{0, 0}, {a, 0}, B, A}, {A, {0, top.y/2}, {0, 0}}, {{a, top.y/2}, B, {a, 0}} }); int p1 = pieces[0]; int p2 = move(pieces[1], {A, C, top}); int p3 = move(pieces[2], {C, B, top}); int tri = tape({p1, p2, p3}, {{0, 0}, {a, 0}, top}); return move(tri, triangle); } vector<vector<pt>> triangulate(vector<pt> polygon) { vector<vector<pt>> res; while (polygon.size() > 3) { int n = polygon.size(); for (int i=0; i<n; i++) { if (orient(polygon[i], polygon[(i+1)%n], polygon[(i+2)%n]) < 0) continue; bool ok = true; for (int j=0; j<n; j++) { if (j == i || j == (i+1)%n || j == (i+2)%n) continue; ok = ok && contains({polygon[i], polygon[(i+1)%n], polygon[(i+2)%n]}, polygon[j]) == 0; } if (ok) { res.push_back({polygon[i], polygon[(i+1)%n], polygon[(i+2)%n]}); polygon.erase(polygon.begin()+(i+1)%n); break; } } } res.push_back(polygon); return res; } int main() { vector<pt> s = read(), t = read(); shapes = {s}; T width = sqrt(area(s)), curheight = 0; vector<int> rectpieces; for (int triangle : scissors(0, triangulate(s))) { int rect = tritorect(triangle, width); rectpieces.push_back(move(rect, genrect(0, width, curheight, curheight + shapes[rect][2].y))); curheight += shapes[rect][2].y; } int combined = tape(rectpieces, genrect(0, width, 0, width)); resize(combined, t[1].x); }

컴파일 시 표준 에러 (stderr) 메시지

scissors.cpp: In function 'void output(std::vector<std::complex<long double> >)':
scissors.cpp:55:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::complex<long double> >::size_type' {aka 'long unsigned int'} [-Wformat=]
   55 |     printf("%d", polygon.size());
      |             ~^   ~~~~~~~~~~~~~~
      |              |               |
      |              int             std::vector<std::complex<long double> >::size_type {aka long unsigned int}
      |             %ld
scissors.cpp: In function 'std::vector<int> scissors(int, std::vector<std::vector<std::complex<long double> > >)':
scissors.cpp:61:27: warning: format '%d' expects argument of type 'int', but argument 3 has type 'std::vector<std::vector<std::complex<long double> > >::size_type' {aka 'long unsigned int'} [-Wformat=]
   61 |     printf("scissors\n%d %d\n", original, pieces.size());
      |                          ~^               ~~~~~~~~~~~~~
      |                           |                          |
      |                           int                        std::vector<std::vector<std::complex<long double> > >::size_type {aka long unsigned int}
      |                          %ld
scissors.cpp: In function 'int tape(std::vector<int>, std::vector<std::complex<long double> >)':
scissors.cpp:72:20: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   72 |     printf("tape\n%d", pieces.size());
      |                   ~^   ~~~~~~~~~~~~~
      |                    |              |
      |                    int            std::vector<int>::size_type {aka long unsigned int}
      |                   %ld
scissors.cpp: In function 'int move(int, std::vector<std::complex<long double> >, int)':
scissors.cpp:84:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::complex<long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (int i=rotatenum; i<loc.size(); i++) pts.push_back(loc[i]);
      |                           ~^~~~~~~~~~~
scissors.cpp: In function 'std::vector<std::complex<long double> > read()':
scissors.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
scissors.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...