oj.uz

Submission #677857

# Submission time Handle Problem Language Result Execution time Memory
677857 2023-01-04T12:54:56 Z Joshc Scissors and Tape (CEOI19_scissors) C++11
100 / 100
 6 ms 484 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 (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);
        rect = resize(rect, width);
        //fprintf(stderr, "Testing: %.6Lf %.6Lf %.6Lf %6.Lf\n", shapes[rect][2].y, shapes[rect][0].x, shapes[rect][1].x, area(shapes[rect]));
        rectpieces.push_back(move(rect, genrect(0, width, curheight, curheight + shapes[rect][2].y)));
        curheight += shapes[rect][2].y;
    }
    //return 0;
    int combined = tape(rectpieces, genrect(0, width, 0, width));
    curheight = 0;
    vector<vector<pt>> rectpieces2, triangulation = triangulate(t);
    for (auto triangle : triangulation) {
        rectpieces2.push_back(genrect(0, width, curheight, curheight+area(triangle)/width));
        curheight += area(triangle)/width;
    }
    vector<int> rects = scissors(combined, rectpieces2), finalpieces;
    for (int i=0; i<rects.size(); i++) {
        int rect = move(rects[i], genrect(0, width, 0, rectpieces2[i][2].y-rectpieces2[i][1].y));
        finalpieces.push_back(recttotri(rect, triangulation[i]));
    }
    tape(finalpieces, t);
}

Compilation message

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 'int main()':
scissors.cpp:238:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  238 |     for (int i=0; i<rects.size(); 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);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 642 vertices, largest error was 0.00000002575449
2 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000030199996
3 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000013533332
4 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000019399998
5 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000030199996
6 Correct 1 ms 304 KB used 698 vertices, largest error was 0.00000001875317
7 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000120199935
8 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000002400000
9 Correct 2 ms 300 KB used 642 vertices, largest error was 0.00000002400000
10 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000019399998

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000008064320
2 Correct 1 ms 340 KB used 662 vertices, largest error was 0.00000307399580
3 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000057650166
4 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000004347702
5 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000004800000
6 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000013150701
7 Correct 1 ms 212 KB used 550 vertices, largest error was 0.00000003200000
8 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000006374210
9 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000006275000
10 Correct 2 ms 212 KB used 550 vertices, largest error was 0.00000011081120

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 642 vertices, largest error was 0.00000002575449
2 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000030199996
3 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000013533332
4 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000019399998
5 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000030199996
6 Correct 1 ms 304 KB used 698 vertices, largest error was 0.00000001875317
7 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000120199935
8 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000002400000
9 Correct 2 ms 300 KB used 642 vertices, largest error was 0.00000002400000
10 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000019399998
11 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000008064320
12 Correct 1 ms 340 KB used 662 vertices, largest error was 0.00000307399580
13 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000057650166
14 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000004347702
15 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000004800000
16 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000013150701
17 Correct 1 ms 212 KB used 550 vertices, largest error was 0.00000003200000
18 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000006374210
19 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000006275000
20 Correct 2 ms 212 KB used 550 vertices, largest error was 0.00000011081120
21 Correct 1 ms 304 KB used 754 vertices, largest error was 0.00000108970434
22 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000012244342
23 Correct 2 ms 340 KB used 698 vertices, largest error was 0.00000003200000
24 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000054791554
25 Correct 1 ms 300 KB used 642 vertices, largest error was 0.00000004800000
26 Correct 2 ms 340 KB used 698 vertices, largest error was 0.00000002866667
27 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000004738430
28 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000003200000
29 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000008812549
30 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000004200000

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000003200000
2 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000002052869
3 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000008454028
4 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000004347702
5 Correct 1 ms 212 KB used 404 vertices, largest error was 0.00000009938108
6 Correct 1 ms 212 KB used 404 vertices, largest error was 0.00000003390678
7 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000036020208
8 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000008637088
9 Correct 1 ms 212 KB used 438 vertices, largest error was 0.00000004298278
10 Correct 1 ms 212 KB used 404 vertices, largest error was 0.00000003200000

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 296 vertices, largest error was 0.00000010553517
2 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000004800000
3 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000003200271
4 Correct 1 ms 212 KB used 352 vertices, largest error was 0.00000004800000
5 Correct 1 ms 340 KB used 380 vertices, largest error was 0.00000003400000
6 Correct 1 ms 212 KB used 324 vertices, largest error was 0.00000004050249
7 Correct 1 ms 212 KB used 380 vertices, largest error was 0.00000008449363
8 Correct 1 ms 212 KB used 346 vertices, largest error was 0.00000004800000
9 Correct 1 ms 212 KB used 324 vertices, largest error was 0.00000007445029
10 Correct 1 ms 212 KB used 324 vertices, largest error was 0.00000003400000

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 642 vertices, largest error was 0.00000002575449
2 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000030199996
3 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000013533332
4 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000019399998
5 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000030199996
6 Correct 1 ms 304 KB used 698 vertices, largest error was 0.00000001875317
7 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000120199935
8 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000002400000
9 Correct 2 ms 300 KB used 642 vertices, largest error was 0.00000002400000
10 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000019399998
11 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000008064320
12 Correct 1 ms 340 KB used 662 vertices, largest error was 0.00000307399580
13 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000057650166
14 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000004347702
15 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000004800000
16 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000013150701
17 Correct 1 ms 212 KB used 550 vertices, largest error was 0.00000003200000
18 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000006374210
19 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000006275000
20 Correct 2 ms 212 KB used 550 vertices, largest error was 0.00000011081120
21 Correct 1 ms 304 KB used 754 vertices, largest error was 0.00000108970434
22 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000012244342
23 Correct 2 ms 340 KB used 698 vertices, largest error was 0.00000003200000
24 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000054791554
25 Correct 1 ms 300 KB used 642 vertices, largest error was 0.00000004800000
26 Correct 2 ms 340 KB used 698 vertices, largest error was 0.00000002866667
27 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000004738430
28 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000003200000
29 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000008812549
30 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000004200000
31 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000003200000
32 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000002052869
33 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000008454028
34 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000004347702
35 Correct 1 ms 212 KB used 404 vertices, largest error was 0.00000009938108
36 Correct 1 ms 212 KB used 404 vertices, largest error was 0.00000003390678
37 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000036020208
38 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000008637088
39 Correct 1 ms 212 KB used 438 vertices, largest error was 0.00000004298278
40 Correct 1 ms 212 KB used 404 vertices, largest error was 0.00000003200000
41 Correct 3 ms 300 KB used 1608 vertices, largest error was 0.00000022806452
42 Correct 2 ms 340 KB used 994 vertices, largest error was 0.00000013837772
43 Correct 4 ms 340 KB used 2390 vertices, largest error was 0.00000013451865
44 Correct 2 ms 340 KB used 1708 vertices, largest error was 0.00000007978848
45 Correct 2 ms 340 KB used 1250 vertices, largest error was 0.00000004800000
46 Correct 2 ms 340 KB used 1022 vertices, largest error was 0.00000005253922
47 Correct 2 ms 340 KB used 988 vertices, largest error was 0.00000004800000
48 Correct 2 ms 340 KB used 1050 vertices, largest error was 0.00000002934058
49 Correct 2 ms 340 KB used 966 vertices, largest error was 0.00000006932463
50 Correct 3 ms 300 KB used 1664 vertices, largest error was 0.00000022018799

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 642 vertices, largest error was 0.00000002575449
2 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000030199996
3 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000013533332
4 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000019399998
5 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000030199996
6 Correct 1 ms 304 KB used 698 vertices, largest error was 0.00000001875317
7 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000120199935
8 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000002400000
9 Correct 2 ms 300 KB used 642 vertices, largest error was 0.00000002400000
10 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000019399998
11 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000008064320
12 Correct 1 ms 340 KB used 662 vertices, largest error was 0.00000307399580
13 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000057650166
14 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000004347702
15 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000004800000
16 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000013150701
17 Correct 1 ms 212 KB used 550 vertices, largest error was 0.00000003200000
18 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000006374210
19 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000006275000
20 Correct 2 ms 212 KB used 550 vertices, largest error was 0.00000011081120
21 Correct 1 ms 304 KB used 754 vertices, largest error was 0.00000108970434
22 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000012244342
23 Correct 2 ms 340 KB used 698 vertices, largest error was 0.00000003200000
24 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000054791554
25 Correct 1 ms 300 KB used 642 vertices, largest error was 0.00000004800000
26 Correct 2 ms 340 KB used 698 vertices, largest error was 0.00000002866667
27 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000004738430
28 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000003200000
29 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000008812549
30 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000004200000
31 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000003200000
32 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000002052869
33 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000008454028
34 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000004347702
35 Correct 1 ms 212 KB used 404 vertices, largest error was 0.00000009938108
36 Correct 1 ms 212 KB used 404 vertices, largest error was 0.00000003390678
37 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000036020208
38 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000008637088
39 Correct 1 ms 212 KB used 438 vertices, largest error was 0.00000004298278
40 Correct 1 ms 212 KB used 404 vertices, largest error was 0.00000003200000
41 Correct 3 ms 300 KB used 1608 vertices, largest error was 0.00000022806452
42 Correct 2 ms 340 KB used 994 vertices, largest error was 0.00000013837772
43 Correct 4 ms 340 KB used 2390 vertices, largest error was 0.00000013451865
44 Correct 2 ms 340 KB used 1708 vertices, largest error was 0.00000007978848
45 Correct 2 ms 340 KB used 1250 vertices, largest error was 0.00000004800000
46 Correct 2 ms 340 KB used 1022 vertices, largest error was 0.00000005253922
47 Correct 2 ms 340 KB used 988 vertices, largest error was 0.00000004800000
48 Correct 2 ms 340 KB used 1050 vertices, largest error was 0.00000002934058
49 Correct 2 ms 340 KB used 966 vertices, largest error was 0.00000006932463
50 Correct 3 ms 300 KB used 1664 vertices, largest error was 0.00000022018799
51 Correct 4 ms 468 KB used 2736 vertices, largest error was 0.00000006799043
52 Correct 4 ms 468 KB used 2642 vertices, largest error was 0.00000032748144
53 Correct 4 ms 340 KB used 1898 vertices, largest error was 0.00000004843646
54 Correct 4 ms 436 KB used 1888 vertices, largest error was 0.00000020430601
55 Correct 3 ms 420 KB used 2094 vertices, largest error was 0.00000007963760
56 Correct 4 ms 468 KB used 2870 vertices, largest error was 0.00000004671263
57 Correct 3 ms 428 KB used 2496 vertices, largest error was 0.00000024585336
58 Correct 4 ms 444 KB used 2976 vertices, largest error was 0.00000011576750
59 Correct 3 ms 436 KB used 2162 vertices, largest error was 0.00000021300408
60 Correct 5 ms 484 KB used 2720 vertices, largest error was 0.00000004800000

Subtask #8
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB used 642 vertices, largest error was 0.00000002575449
2 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000030199996
3 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000013533332
4 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000019399998
5 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000030199996
6 Correct 1 ms 304 KB used 698 vertices, largest error was 0.00000001875317
7 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000120199935
8 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000002400000
9 Correct 2 ms 300 KB used 642 vertices, largest error was 0.00000002400000
10 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000019399998
11 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000008064320
12 Correct 1 ms 340 KB used 662 vertices, largest error was 0.00000307399580
13 Correct 1 ms 340 KB used 606 vertices, largest error was 0.00000057650166
14 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000004347702
15 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000004800000
16 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000013150701
17 Correct 1 ms 212 KB used 550 vertices, largest error was 0.00000003200000
18 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000006374210
19 Correct 1 ms 340 KB used 550 vertices, largest error was 0.00000006275000
20 Correct 2 ms 212 KB used 550 vertices, largest error was 0.00000011081120
21 Correct 1 ms 304 KB used 754 vertices, largest error was 0.00000108970434
22 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000012244342
23 Correct 2 ms 340 KB used 698 vertices, largest error was 0.00000003200000
24 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000054791554
25 Correct 1 ms 300 KB used 642 vertices, largest error was 0.00000004800000
26 Correct 2 ms 340 KB used 698 vertices, largest error was 0.00000002866667
27 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000004738430
28 Correct 1 ms 340 KB used 642 vertices, largest error was 0.00000003200000
29 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000008812549
30 Correct 1 ms 340 KB used 698 vertices, largest error was 0.00000004200000
31 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000003200000
32 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000002052869
33 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000008454028
34 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000004347702
35 Correct 1 ms 212 KB used 404 vertices, largest error was 0.00000009938108
36 Correct 1 ms 212 KB used 404 vertices, largest error was 0.00000003390678
37 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000036020208
38 Correct 1 ms 212 KB used 410 vertices, largest error was 0.00000008637088
39 Correct 1 ms 212 KB used 438 vertices, largest error was 0.00000004298278
40 Correct 1 ms 212 KB used 404 vertices, largest error was 0.00000003200000
41 Correct 1 ms 212 KB used 296 vertices, largest error was 0.00000010553517
42 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000004800000
43 Correct 1 ms 212 KB used 318 vertices, largest error was 0.00000003200271
44 Correct 1 ms 212 KB used 352 vertices, largest error was 0.00000004800000
45 Correct 1 ms 340 KB used 380 vertices, largest error was 0.00000003400000
46 Correct 1 ms 212 KB used 324 vertices, largest error was 0.00000004050249
47 Correct 1 ms 212 KB used 380 vertices, largest error was 0.00000008449363
48 Correct 1 ms 212 KB used 346 vertices, largest error was 0.00000004800000
49 Correct 1 ms 212 KB used 324 vertices, largest error was 0.00000007445029
50 Correct 1 ms 212 KB used 324 vertices, largest error was 0.00000003400000
51 Correct 3 ms 300 KB used 1608 vertices, largest error was 0.00000022806452
52 Correct 2 ms 340 KB used 994 vertices, largest error was 0.00000013837772
53 Correct 4 ms 340 KB used 2390 vertices, largest error was 0.00000013451865
54 Correct 2 ms 340 KB used 1708 vertices, largest error was 0.00000007978848
55 Correct 2 ms 340 KB used 1250 vertices, largest error was 0.00000004800000
56 Correct 2 ms 340 KB used 1022 vertices, largest error was 0.00000005253922
57 Correct 2 ms 340 KB used 988 vertices, largest error was 0.00000004800000
58 Correct 2 ms 340 KB used 1050 vertices, largest error was 0.00000002934058
59 Correct 2 ms 340 KB used 966 vertices, largest error was 0.00000006932463
60 Correct 3 ms 300 KB used 1664 vertices, largest error was 0.00000022018799
61 Correct 4 ms 468 KB used 2736 vertices, largest error was 0.00000006799043
62 Correct 4 ms 468 KB used 2642 vertices, largest error was 0.00000032748144
63 Correct 4 ms 340 KB used 1898 vertices, largest error was 0.00000004843646
64 Correct 4 ms 436 KB used 1888 vertices, largest error was 0.00000020430601
65 Correct 3 ms 420 KB used 2094 vertices, largest error was 0.00000007963760
66 Correct 4 ms 468 KB used 2870 vertices, largest error was 0.00000004671263
67 Correct 3 ms 428 KB used 2496 vertices, largest error was 0.00000024585336
68 Correct 4 ms 444 KB used 2976 vertices, largest error was 0.00000011576750
69 Correct 3 ms 436 KB used 2162 vertices, largest error was 0.00000021300408
70 Correct 5 ms 484 KB used 2720 vertices, largest error was 0.00000004800000
71 Correct 6 ms 448 KB used 3998 vertices, largest error was 0.00000024188446
72 Correct 5 ms 424 KB used 3266 vertices, largest error was 0.00000019029896
73 Correct 5 ms 468 KB used 3994 vertices, largest error was 0.00000011265425
74 Correct 4 ms 468 KB used 3158 vertices, largest error was 0.00000014988189
75 Correct 5 ms 472 KB used 3632 vertices, largest error was 0.00000021065897
76 Correct 5 ms 480 KB used 3430 vertices, largest error was 0.00000016938564
77 Correct 5 ms 468 KB used 3294 vertices, largest error was 0.00000032988119
78 Correct 5 ms 468 KB used 4162 vertices, largest error was 0.00000015675955
79 Correct 6 ms 468 KB used 4140 vertices, largest error was 0.00000028216535