이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 (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;
}
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 main() {
vector<pt> S = read(), T = read();
shapes = {S};
if (S.size() == 4) resize(0, T[1].x-T[0].x);
else tritorect(0, T[1].x);
}
컴파일 시 표준 에러 (stderr) 메시지
scissors.cpp: In function 'void output(std::vector<std::complex<long double> >)':
scissors.cpp:44: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=]
44 | 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:50: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=]
50 | 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:61:20: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
61 | 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:73: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]
73 | 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:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
scissors.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |