oj.uz

Submission #677228

# Submission time Handle Problem Language Result Execution time Memory
677228 2023-01-02T15:18:51 Z Joshc Scissors and Tape (CEOI19_scissors) C++11
30 / 100
 1000 ms 23264 KB 
#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, bool rotaterect = false) {
    printf("tape\n1 %d\n", shape);
    if (rotaterect) output({loc[1], loc[2], loc[3], loc[0]});
    else output(loc);
    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), true);
    }
    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), true);
        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));
}
 
int main() {
    vector<pt> S = read(), T = read();
    shapes = {S};   
    resize(0, T[1].x-T[0].x);
}

Compilation message

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 'std::vector<std::complex<long double> > read()':
scissors.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
scissors.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
2 Correct 0 ms 296 KB used 82 vertices, largest error was 0.00000001600000
3 Correct 0 ms 212 KB used 44 vertices, largest error was 0.00000000800000
4 Correct 0 ms 212 KB used 36 vertices, largest error was 0.00000000800000
5 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
6 Correct 1 ms 304 KB used 36 vertices, largest error was 0.00000000800000
7 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
8 Correct 0 ms 212 KB used 46 vertices, largest error was 0.00000001600000
9 Correct 1 ms 212 KB used 36 vertices, largest error was 0.00000000800000
10 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
2 Correct 1 ms 212 KB used 64 vertices, largest error was 0.00000000800000
3 Correct 0 ms 212 KB used 74 vertices, largest error was 0.00000003200000
4 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000206199551
5 Correct 1 ms 348 KB used 46 vertices, largest error was 0.00000001783721
6 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000004331465
7 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
8 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000002059268
9 Correct 1 ms 304 KB used 46 vertices, largest error was 0.00000003683333
10 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
2 Correct 0 ms 296 KB used 82 vertices, largest error was 0.00000001600000
3 Correct 0 ms 212 KB used 44 vertices, largest error was 0.00000000800000
4 Correct 0 ms 212 KB used 36 vertices, largest error was 0.00000000800000
5 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
6 Correct 1 ms 304 KB used 36 vertices, largest error was 0.00000000800000
7 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
8 Correct 0 ms 212 KB used 46 vertices, largest error was 0.00000001600000
9 Correct 1 ms 212 KB used 36 vertices, largest error was 0.00000000800000
10 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
11 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
12 Correct 1 ms 212 KB used 64 vertices, largest error was 0.00000000800000
13 Correct 0 ms 212 KB used 74 vertices, largest error was 0.00000003200000
14 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000206199551
15 Correct 1 ms 348 KB used 46 vertices, largest error was 0.00000001783721
16 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000004331465
17 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
18 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000002059268
19 Correct 1 ms 304 KB used 46 vertices, largest error was 0.00000003683333
20 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
21 Correct 0 ms 212 KB used 54 vertices, largest error was 0.00000002747332
22 Correct 1 ms 212 KB used 82 vertices, largest error was 0.00000003200000
23 Correct 0 ms 212 KB used 46 vertices, largest error was 0.00000001994111
24 Correct 1 ms 212 KB used 102 vertices, largest error was 0.00000001994975
25 Correct 1 ms 296 KB used 62 vertices, largest error was 0.00000001600000
26 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000002274266
27 Correct 0 ms 212 KB used 46 vertices, largest error was 0.00000001600000
28 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000002830679
29 Correct 1 ms 212 KB used 102 vertices, largest error was 0.00000003200000
30 Correct 1 ms 296 KB used 110 vertices, largest error was 0.00000003400000

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Operation 1, Polygon 0: Polygon given in clockwise order, must be counter-clockwise
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 23264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
2 Correct 0 ms 296 KB used 82 vertices, largest error was 0.00000001600000
3 Correct 0 ms 212 KB used 44 vertices, largest error was 0.00000000800000
4 Correct 0 ms 212 KB used 36 vertices, largest error was 0.00000000800000
5 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
6 Correct 1 ms 304 KB used 36 vertices, largest error was 0.00000000800000
7 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
8 Correct 0 ms 212 KB used 46 vertices, largest error was 0.00000001600000
9 Correct 1 ms 212 KB used 36 vertices, largest error was 0.00000000800000
10 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
11 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
12 Correct 1 ms 212 KB used 64 vertices, largest error was 0.00000000800000
13 Correct 0 ms 212 KB used 74 vertices, largest error was 0.00000003200000
14 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000206199551
15 Correct 1 ms 348 KB used 46 vertices, largest error was 0.00000001783721
16 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000004331465
17 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
18 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000002059268
19 Correct 1 ms 304 KB used 46 vertices, largest error was 0.00000003683333
20 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
21 Correct 0 ms 212 KB used 54 vertices, largest error was 0.00000002747332
22 Correct 1 ms 212 KB used 82 vertices, largest error was 0.00000003200000
23 Correct 0 ms 212 KB used 46 vertices, largest error was 0.00000001994111
24 Correct 1 ms 212 KB used 102 vertices, largest error was 0.00000001994975
25 Correct 1 ms 296 KB used 62 vertices, largest error was 0.00000001600000
26 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000002274266
27 Correct 0 ms 212 KB used 46 vertices, largest error was 0.00000001600000
28 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000002830679
29 Correct 1 ms 212 KB used 102 vertices, largest error was 0.00000003200000
30 Correct 1 ms 296 KB used 110 vertices, largest error was 0.00000003400000
31 Incorrect 1 ms 212 KB Operation 1, Polygon 0: Polygon given in clockwise order, must be counter-clockwise
32 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
2 Correct 0 ms 296 KB used 82 vertices, largest error was 0.00000001600000
3 Correct 0 ms 212 KB used 44 vertices, largest error was 0.00000000800000
4 Correct 0 ms 212 KB used 36 vertices, largest error was 0.00000000800000
5 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
6 Correct 1 ms 304 KB used 36 vertices, largest error was 0.00000000800000
7 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
8 Correct 0 ms 212 KB used 46 vertices, largest error was 0.00000001600000
9 Correct 1 ms 212 KB used 36 vertices, largest error was 0.00000000800000
10 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
11 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
12 Correct 1 ms 212 KB used 64 vertices, largest error was 0.00000000800000
13 Correct 0 ms 212 KB used 74 vertices, largest error was 0.00000003200000
14 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000206199551
15 Correct 1 ms 348 KB used 46 vertices, largest error was 0.00000001783721
16 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000004331465
17 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
18 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000002059268
19 Correct 1 ms 304 KB used 46 vertices, largest error was 0.00000003683333
20 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
21 Correct 0 ms 212 KB used 54 vertices, largest error was 0.00000002747332
22 Correct 1 ms 212 KB used 82 vertices, largest error was 0.00000003200000
23 Correct 0 ms 212 KB used 46 vertices, largest error was 0.00000001994111
24 Correct 1 ms 212 KB used 102 vertices, largest error was 0.00000001994975
25 Correct 1 ms 296 KB used 62 vertices, largest error was 0.00000001600000
26 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000002274266
27 Correct 0 ms 212 KB used 46 vertices, largest error was 0.00000001600000
28 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000002830679
29 Correct 1 ms 212 KB used 102 vertices, largest error was 0.00000003200000
30 Correct 1 ms 296 KB used 110 vertices, largest error was 0.00000003400000
31 Incorrect 1 ms 212 KB Operation 1, Polygon 0: Polygon given in clockwise order, must be counter-clockwise
32 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
2 Correct 0 ms 296 KB used 82 vertices, largest error was 0.00000001600000
3 Correct 0 ms 212 KB used 44 vertices, largest error was 0.00000000800000
4 Correct 0 ms 212 KB used 36 vertices, largest error was 0.00000000800000
5 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
6 Correct 1 ms 304 KB used 36 vertices, largest error was 0.00000000800000
7 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
8 Correct 0 ms 212 KB used 46 vertices, largest error was 0.00000001600000
9 Correct 1 ms 212 KB used 36 vertices, largest error was 0.00000000800000
10 Correct 1 ms 212 KB used 44 vertices, largest error was 0.00000000800000
11 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
12 Correct 1 ms 212 KB used 64 vertices, largest error was 0.00000000800000
13 Correct 0 ms 212 KB used 74 vertices, largest error was 0.00000003200000
14 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000206199551
15 Correct 1 ms 348 KB used 46 vertices, largest error was 0.00000001783721
16 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000004331465
17 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
18 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000002059268
19 Correct 1 ms 304 KB used 46 vertices, largest error was 0.00000003683333
20 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000001600000
21 Correct 0 ms 212 KB used 54 vertices, largest error was 0.00000002747332
22 Correct 1 ms 212 KB used 82 vertices, largest error was 0.00000003200000
23 Correct 0 ms 212 KB used 46 vertices, largest error was 0.00000001994111
24 Correct 1 ms 212 KB used 102 vertices, largest error was 0.00000001994975
25 Correct 1 ms 296 KB used 62 vertices, largest error was 0.00000001600000
26 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000002274266
27 Correct 0 ms 212 KB used 46 vertices, largest error was 0.00000001600000
28 Correct 1 ms 212 KB used 46 vertices, largest error was 0.00000002830679
29 Correct 1 ms 212 KB used 102 vertices, largest error was 0.00000003200000
30 Correct 1 ms 296 KB used 110 vertices, largest error was 0.00000003400000
31 Incorrect 1 ms 212 KB Operation 1, Polygon 0: Polygon given in clockwise order, must be counter-clockwise
32 Halted 0 ms 0 KB -