oj.uz

Submission #198124

# Submission time Handle Problem Language Result Execution time Memory
198124 2020-01-24T18:33:25 Z model_code Scissors and Tape (CEOI19_scissors) C++17
100 / 100
 13 ms 448 KB 
#include <algorithm>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

// universal geometric functions

typedef double rational;
typedef complex<rational> point;
typedef vector<point> poly;

const rational EPSILON = 1e-9;

bool is_negative(rational x) { return x < -EPSILON; }
bool is_zero(rational x) { return abs(x) <= EPSILON; }
bool is_positive(rational x) { return x > EPSILON; }
bool are_equal(rational x, rational y) { 
    if (is_zero(x-y)) return true;
    rational lo = min( x*(1-EPSILON), x*(1+EPSILON) ), hi = max( x*(1-EPSILON), x*(1+EPSILON) );
    return (lo <= y && y <= hi);
}
bool are_equal(const vector<rational> &A, const vector<rational> &B) {
    if (A.size() != B.size()) return false;
    for (unsigned n=0; n<A.size(); ++n) if (!are_equal(A[n],B[n])) return false;
    return true;
}
bool are_equal(const point &A, const point &B) { return is_zero(real(B)-real(A)) && is_zero(imag(B)-imag(A)); }
int signum(rational x) { if (is_zero(x)) return 0; if (is_negative(x)) return -1; return 1; }
rational square_size  (const point &A)                 { return real(A) * real(A) + imag(A) * imag(A); }
rational dot_product  (const point &A, const point &B) { return real(A) * real(B) + imag(A) * imag(B); }
rational cross_product(const point &A, const point &B) { return real(A) * imag(B) - real(B) * imag(A); }
rational size(const point &A) { return sqrt(real(A) * real(A) + imag(A) * imag(A)); }
void normalize(point &A) { rational Asize = size(A); A *= (1/Asize); }
bool colinear(const point &A, const point &B, const point &C) { return is_zero( cross_product( B-A, C-A )); }
bool colinear(const point &B, const point &C)                 { return is_zero( cross_product( B,   C ));   }
bool clockwise(const point &A, const point &B, const point &C) { return is_negative( cross_product( B-A, C-A )); }
bool clockwise(const point &B, const point &C)                 { return is_negative( cross_product( B,   C ));   }
bool counterclockwise(const point &A, const point &B, const point &C) { return is_positive( cross_product( B-A, C-A )); }
bool counterclockwise(const point &B, const point &C)                 { return is_positive( cross_product( B,   C ));   }

rational poly_area(const poly &V) { 
    rational res = 0;
    for (unsigned i=0; i<V.size(); i++) res += cross_product( V[i], V[(i+1)%V.size()] ); 
    return abs(0.5 * res);
}

vector<rational> side_lengths(const poly &P) {
    int N = P.size();
    vector<rational> answer;
    for (int n=0; n<N; ++n) answer.push_back( size( P[(n+1)%N] - P[n] ) );
    return answer;
}

// task-specific functions

int NEXT_ID;

struct object {
    int ID;
    poly P;
    object(const poly &P) : P(P) { ID = NEXT_ID++; }
};

void initialize() {
    NEXT_ID = 0;
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);
}

void print_poly(const poly &P) { 
    cout << P.size(); 
    for (auto pt : P) cout << " " << real(pt) << " " << imag(pt);
    cout << endl;
}

poly load_poly() {
    int N; cin >> N;
    poly P(N);
    rational x, y;
    for (int n=0; n<N; ++n) { cin >> x >> y; P[n] = point(x,y); }
    return P;
}

poly nice_rectangle(rational x, rational y, rational dx = 0, rational dy = 0) { return { point(dx,dy), point(dx+x,dy), point(dx+x,dy+y), point(dx,dy+y) }; }

void cut_and_paste(int startWith, const vector<poly> &cutInto, const vector<poly> &rearrangeInto, const poly &endWith) {
    cout << "scissors" << endl << startWith << " " << cutInto.size() << endl;
    vector<int> new_ids;
    for (const auto &piece : cutInto) { new_ids.push_back( NEXT_ID++ ); print_poly(piece); }
    cout << "tape" << endl << rearrangeInto.size();
    for (int x : new_ids) cout << " " << x;
    cout << endl;
    for (const auto &piece : rearrangeInto) print_poly(piece);
    print_poly(endWith);
}

object nice_rectangle_to_nice_rectangle(object Rin, const poly &Rout) {
    while (true) {
        rational x1 = real(Rin.P[2]), y1 = imag(Rin.P[2]), x2 = real(Rout[2]), y2 = imag(Rout[2]);
        
        if (are_equal(x1,x2)) return Rin;

        if (!is_negative(x1 - 2*x2)) { // x1 is at least twice as big, fold in half
            cut_and_paste( 
                    Rin.ID, 
                    { nice_rectangle( x1/2, y1 ), nice_rectangle( x1/2, y1, x1/2,  0 ) },
                    { nice_rectangle( x1/2, y1 ), nice_rectangle( x1/2, y1,    0, y1 ) },
                    nice_rectangle( x1/2,y1*2 )
            );
            Rin = object(nice_rectangle(x1/2,y1*2));
            continue;
        }

        if (!is_negative(y1 - 2*y2)) { // y1 is at least twice as big, fold in half
            cut_and_paste(
                    Rin.ID, 
                    { nice_rectangle( x1, y1/2 ), nice_rectangle( x1, y1/2,  0, y1/2 ) },
                    { nice_rectangle( x1, y1/2 ), nice_rectangle( x1, y1/2, x1,    0 ) },
                    nice_rectangle( x1*2,y1/2 )
            );
            Rin = object(nice_rectangle(x1*2,y1/2));
            continue;
        }

        if (is_positive(x1 - x2)) { // x1 is at most twice as big, cut into three and reassemble
            rational offx = x1 - x2, offy = y1 * offx / x2;
            cut_and_paste(
                    Rin.ID,
                    { { point(0,0), point(x2,y1), point(0,y1) },    { point(0,0), point(offx,0), point(offx,offy) },   { point(offx,0), point(x1,0), point(x1,y1), point(x2,y1), point(offx,offy) } },
                    { { point(0,offy), point(x2,y2), point(0,y2) }, { point(x2-offx,y1), point(x2,y1), point(x2,y2) }, { point(0,0), point(x2,0), point(x2,y1), point(x2-offx,y1), point(0,offy) }  },
                    nice_rectangle(x2,y2)
            );
            return object(Rout);
        } else { // y1 is at most twice as big, cut into three and reassemble
            rational offy = y1 - y2, offx = x1 * offy / y2;
            cut_and_paste(
                    Rin.ID,
                    { { point(0,0), point(x1,0), point(x1,y2) },    { point(0,0), point(offx,offy), point(0,offy) },             { point(0,offy), point(offx,offy), point(x1,y2), point(x1,y1), point(0,y1) } },
                    { { point(offx,0), point(x2,0), point(x2,y2) }, { point(x2-offx,y2-offy), point(x2,y2), point(x2-offx,y2) }, { point(0,0), point(offx,0), point(x1,y2-offy), point(x1,y2), point(0,y2) }  },
                    nice_rectangle(x2,y2)
            );
            return object(Rout);
        }
    }
}

pair<poly,poly> triangle_to_nice_triangle(const poly &P) {
    vector<double> sides = side_lengths(P);
    vector<double> tmp = sides;
    int offset = 0;
    rotate( tmp.begin(), tmp.begin()+1, tmp.end() ); if (tmp > sides) sides = tmp, offset = 2;
    rotate( tmp.begin(), tmp.begin()+1, tmp.end() ); if (tmp > sides) sides = tmp, offset = 1;
    rational x = sides[0], y = sides[1], z = sides[2], cx = (x*x + z*z - y*y) / (2*x), cy = sqrt( z*z - cx*cx );
    poly target{ point(0,0), point(x,0), point(cx,cy) };
    poly source{ target[offset], target[(offset+1)%3], target[(offset+2)%3] };
    return {source, target};
}

object triangle_to_nice_triangle(const object &Tin) {
    auto nice = triangle_to_nice_triangle(Tin.P); 
    cout << "tape" << endl;
    cout << "1 " << Tin.ID << endl;
    print_poly(nice.first);
    print_poly(nice.second);
    return object(nice.second);
}

object nice_triangle_to_nice_rectangle(const object &Tin) {
    rational x = real(Tin.P[1]), cx = real(Tin.P[2]), cy = imag(Tin.P[2]);
    cut_and_paste(
            Tin.ID,
            { { point(0,0), point(x,0), point((x+cx)/2,cy/2), point(cx/2,cy/2) }, { point(cx,cy/2), point((x+cx)/2,cy/2), point(cx,cy) }, { point(cx/2,cy/2), point(cx,cy/2), point(cx,cy) } },
            { { point(0,0), point(x,0), point((x+cx)/2,cy/2), point(cx/2,cy/2) }, { point(x,cy/2), point((x+cx)/2,cy/2), point(x,0) },    { point(cx/2,cy/2), point(0,cy/2), point(0,0) }    },
            nice_rectangle(x,cy/2)
    );
    return object(nice_rectangle(x,cy/2));
}

object rectangle_to_nice_triangle(const object &Rin, const poly &tri) {
    poly nice = triangle_to_nice_triangle(tri).second; 
    rational x = real(nice[1]), cx = real(nice[2]), cy = imag(nice[2]);
    
    // normalize the rectangle
    cout << "tape" << endl;
    cout << "1 " << Rin.ID << endl;
    rational width = real(Rin.P[2]) - real(Rin.P[0]), height = imag(Rin.P[2]) - imag(Rin.P[0]);
    print_poly( nice_rectangle(width,height) );
    print_poly( nice_rectangle(width,height) );
    object rect(nice_rectangle(width,height));

    // resize the rectangle
    rect = nice_rectangle_to_nice_rectangle(rect,nice_rectangle(x,width*height/x));

    // cut the rectangle and assemble the triangle
    cut_and_paste(
            rect.ID,
            { { point(0,0), point(x,0), point((x+cx)/2,cy/2), point(cx/2,cy/2) }, { point(x,cy/2), point((x+cx)/2,cy/2), point(x,0) },    { point(cx/2,cy/2), point(0,cy/2), point(0,0) }    },
            { { point(0,0), point(x,0), point((x+cx)/2,cy/2), point(cx/2,cy/2) }, { point(cx,cy/2), point((x+cx)/2,cy/2), point(cx,cy) }, { point(cx/2,cy/2), point(cx,cy/2), point(cx,cy) } },
            nice
    );
    return object(nice);
}

bool is_triangle_ear(const poly &P, point A, point B, point C) {
    if (!counterclockwise(A,B,C)) return false;
    for (point X : P) {
        if (are_equal(A,X) || are_equal(B,X) || are_equal(C,X)) continue;
        if (counterclockwise(A,B,X) && counterclockwise(B,C,X) && counterclockwise(C,A,X)) return false;
    }
    return true;
}

vector<poly> triangulate(poly P) {
    int N = P.size();
    if (N == 3) return {P};
    for (int n=0; n<N; ++n) if (is_triangle_ear(P,P[n],P[(n+1)%N],P[(n+2)%N])) {
        poly Q = P;
        Q.erase( Q.begin()+(n+1)%N );
        vector<poly> answer = triangulate(Q);
        answer.push_back( {P[n],P[(n+1)%N],P[(n+2)%N]} );
        return answer;
    }
    assert(false);
}

vector<object> triangulate_input(const object &Pin) {
    int N = Pin.P.size();
    cout << "scissors" << endl;
    cout << Pin.ID << " " << N-2 << endl;

    vector<object> answer;
    for (poly troj : triangulate(Pin.P)) {
        print_poly(troj);
        answer.push_back(object(troj));
    }
    return answer; 
}

object merge_rectangulation(const vector<object> &RECT) {
    cout << "tape" << endl;
    cout << RECT.size();
    for (auto rect : RECT) cout << " " << rect.ID;
    cout << endl;
    rational dx = 0;
    for (auto rect : RECT) {
        auto P = rect.P;
        rational width = real(P[2]);
        for (auto &pt : P) pt += dx;
        print_poly(P);
        dx += width;
    }
    print_poly(nice_rectangle(dx,dx));
    return object(nice_rectangle(dx,dx));
}

vector<object> split_square(const object &Sin, const vector<poly> &pieces) {
    rational a = real(Sin.P[2]), dx = 0;
    cout << "scissors" << endl;
    cout << Sin.ID << " " << pieces.size() << endl;
    vector<object> answer;
    for (auto tri : pieces) {
        rational width = poly_area(tri) / a;
        auto rect = nice_rectangle(width,a,dx,0);
        print_poly(rect);
        answer.push_back(object(rect));
        dx += width;
    }
    return answer;
}

void merge_triangulation(const vector<object> &have, vector<poly> &want, poly &goal) {
    int N = have.size();
    cout << "tape" << endl;
    cout << N;
    for (auto tri : have) cout << " " << tri.ID;
    cout << endl;
    for (int n=0; n<N; ++n) {
        auto havelen = side_lengths(have[n].P);
        while (true) {
            auto wantlen = side_lengths(want[n]);
            if (are_equal(havelen,wantlen)) break;
            rotate( want[n].begin(), want[n].begin()+1, want[n].end() );
        }
        print_poly(want[n]);
    }
    print_poly(goal);
}

int main() {
    initialize();
    poly start = load_poly();
    poly goal = load_poly();
    object START(start);
    vector<object> TRIANGULATION = triangulate_input(START);
    rational area = poly_area(start);
    rational desired_y = sqrt(area);
    vector<object> RECTANGULATION;
    for (auto tri : TRIANGULATION) {
        object nicetri = triangle_to_nice_triangle(tri);
        object rect = nice_triangle_to_nice_rectangle(nicetri);
        rational rect_area = poly_area(rect.P);
        object rect2 = nice_rectangle_to_nice_rectangle(rect,nice_rectangle(rect_area/desired_y,desired_y));
        RECTANGULATION.push_back(rect2);
    }
    object square = merge_rectangulation(RECTANGULATION);
    vector<poly> output_triangulation = triangulate(goal);
    RECTANGULATION = split_square(square,output_triangulation);
    TRIANGULATION.clear();
    for (unsigned n=0; n<output_triangulation.size(); ++n) TRIANGULATION.push_back(rectangle_to_nice_triangle(RECTANGULATION[n],output_triangulation[n]));
    merge_triangulation(TRIANGULATION,output_triangulation,goal);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000008111111
2 Correct 3 ms 380 KB used 390 vertices, largest error was 0.00000030199996
3 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000013533332
4 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000045889391
5 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000030199996
6 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000025999999
7 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000120199935
8 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012111111
9 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012111111
10 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000033092428

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000008442880
2 Correct 4 ms 376 KB used 430 vertices, largest error was 0.00000717898774
3 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000057650166
4 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
5 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
6 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000013150701
7 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
8 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000006374210
9 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000006275000
10 Correct 13 ms 376 KB used 350 vertices, largest error was 0.00000011081120

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000008111111
2 Correct 3 ms 380 KB used 390 vertices, largest error was 0.00000030199996
3 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000013533332
4 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000045889391
5 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000030199996
6 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000025999999
7 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000120199935
8 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012111111
9 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012111111
10 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000033092428
11 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000008442880
12 Correct 4 ms 376 KB used 430 vertices, largest error was 0.00000717898774
13 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000057650166
14 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
15 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
16 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000013150701
17 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
18 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000006374210
19 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000006275000
20 Correct 13 ms 376 KB used 350 vertices, largest error was 0.00000011081120
21 Correct 4 ms 376 KB used 430 vertices, largest error was 0.00000108970434
22 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012244342
23 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000025256908
24 Correct 4 ms 376 KB used 390 vertices, largest error was 0.00000054791554
25 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004234995
26 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000040731849
27 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004738430
28 Correct 4 ms 376 KB used 350 vertices, largest error was 0.00000004683774
29 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000148940376
30 Correct 4 ms 376 KB used 390 vertices, largest error was 0.00000070293978

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000009951180
2 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000024648484
3 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000008454028
4 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000004662742
5 Correct 3 ms 256 KB used 266 vertices, largest error was 0.00000009938108
6 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000004662742
7 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000036020209
8 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000008501079
9 Correct 3 ms 376 KB used 286 vertices, largest error was 0.00000004662742
10 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000019841817

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 376 KB used 160 vertices, largest error was 0.00000010553517
2 Correct 3 ms 376 KB used 180 vertices, largest error was 0.00000004307537
3 Correct 3 ms 376 KB used 180 vertices, largest error was 0.00000003252115
4 Correct 3 ms 376 KB used 200 vertices, largest error was 0.00000013351743
5 Correct 4 ms 256 KB used 220 vertices, largest error was 0.00000036628725
6 Correct 3 ms 256 KB used 180 vertices, largest error was 0.00000013056731
7 Correct 3 ms 376 KB used 220 vertices, largest error was 0.00000012402993
8 Correct 3 ms 376 KB used 200 vertices, largest error was 0.00000013676669
9 Correct 3 ms 376 KB used 180 vertices, largest error was 0.00000060296770
10 Correct 3 ms 376 KB used 180 vertices, largest error was 0.00000054043226

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000008111111
2 Correct 3 ms 380 KB used 390 vertices, largest error was 0.00000030199996
3 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000013533332
4 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000045889391
5 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000030199996
6 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000025999999
7 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000120199935
8 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012111111
9 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012111111
10 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000033092428
11 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000008442880
12 Correct 4 ms 376 KB used 430 vertices, largest error was 0.00000717898774
13 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000057650166
14 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
15 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
16 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000013150701
17 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
18 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000006374210
19 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000006275000
20 Correct 13 ms 376 KB used 350 vertices, largest error was 0.00000011081120
21 Correct 4 ms 376 KB used 430 vertices, largest error was 0.00000108970434
22 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012244342
23 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000025256908
24 Correct 4 ms 376 KB used 390 vertices, largest error was 0.00000054791554
25 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004234995
26 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000040731849
27 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004738430
28 Correct 4 ms 376 KB used 350 vertices, largest error was 0.00000004683774
29 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000148940376
30 Correct 4 ms 376 KB used 390 vertices, largest error was 0.00000070293978
31 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000009951180
32 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000024648484
33 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000008454028
34 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000004662742
35 Correct 3 ms 256 KB used 266 vertices, largest error was 0.00000009938108
36 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000004662742
37 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000036020209
38 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000008501079
39 Correct 3 ms 376 KB used 286 vertices, largest error was 0.00000004662742
40 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000019841817
41 Correct 5 ms 376 KB used 722 vertices, largest error was 0.00000030454489
42 Correct 4 ms 376 KB used 474 vertices, largest error was 0.00000013837772
43 Correct 6 ms 376 KB used 990 vertices, largest error was 0.00000013451865
44 Correct 5 ms 376 KB used 742 vertices, largest error was 0.00000015254838
45 Correct 4 ms 376 KB used 578 vertices, largest error was 0.00000006707106
46 Correct 4 ms 376 KB used 494 vertices, largest error was 0.00000013877504
47 Correct 4 ms 376 KB used 474 vertices, largest error was 0.00000008819415
48 Correct 4 ms 376 KB used 494 vertices, largest error was 0.00000030033285
49 Correct 4 ms 368 KB used 474 vertices, largest error was 0.00000006932463
50 Correct 3 ms 376 KB used 722 vertices, largest error was 0.00000022018799

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000008111111
2 Correct 3 ms 380 KB used 390 vertices, largest error was 0.00000030199996
3 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000013533332
4 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000045889391
5 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000030199996
6 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000025999999
7 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000120199935
8 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012111111
9 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012111111
10 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000033092428
11 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000008442880
12 Correct 4 ms 376 KB used 430 vertices, largest error was 0.00000717898774
13 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000057650166
14 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
15 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
16 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000013150701
17 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
18 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000006374210
19 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000006275000
20 Correct 13 ms 376 KB used 350 vertices, largest error was 0.00000011081120
21 Correct 4 ms 376 KB used 430 vertices, largest error was 0.00000108970434
22 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012244342
23 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000025256908
24 Correct 4 ms 376 KB used 390 vertices, largest error was 0.00000054791554
25 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004234995
26 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000040731849
27 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004738430
28 Correct 4 ms 376 KB used 350 vertices, largest error was 0.00000004683774
29 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000148940376
30 Correct 4 ms 376 KB used 390 vertices, largest error was 0.00000070293978
31 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000009951180
32 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000024648484
33 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000008454028
34 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000004662742
35 Correct 3 ms 256 KB used 266 vertices, largest error was 0.00000009938108
36 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000004662742
37 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000036020209
38 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000008501079
39 Correct 3 ms 376 KB used 286 vertices, largest error was 0.00000004662742
40 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000019841817
41 Correct 5 ms 376 KB used 722 vertices, largest error was 0.00000030454489
42 Correct 4 ms 376 KB used 474 vertices, largest error was 0.00000013837772
43 Correct 6 ms 376 KB used 990 vertices, largest error was 0.00000013451865
44 Correct 5 ms 376 KB used 742 vertices, largest error was 0.00000015254838
45 Correct 4 ms 376 KB used 578 vertices, largest error was 0.00000006707106
46 Correct 4 ms 376 KB used 494 vertices, largest error was 0.00000013877504
47 Correct 4 ms 376 KB used 474 vertices, largest error was 0.00000008819415
48 Correct 4 ms 376 KB used 494 vertices, largest error was 0.00000030033285
49 Correct 4 ms 368 KB used 474 vertices, largest error was 0.00000006932463
50 Correct 3 ms 376 KB used 722 vertices, largest error was 0.00000022018799
51 Correct 6 ms 376 KB used 1134 vertices, largest error was 0.00000008072091
52 Correct 6 ms 376 KB used 1150 vertices, largest error was 0.00000066405194
53 Correct 6 ms 372 KB used 842 vertices, largest error was 0.00000023500389
54 Correct 5 ms 376 KB used 842 vertices, largest error was 0.00000240827671
55 Correct 5 ms 376 KB used 926 vertices, largest error was 0.00000126282600
56 Correct 6 ms 376 KB used 1214 vertices, largest error was 0.00000200539773
57 Correct 6 ms 376 KB used 1070 vertices, largest error was 0.00000080974555
58 Correct 7 ms 376 KB used 1234 vertices, largest error was 0.00000037878823
59 Correct 6 ms 376 KB used 966 vertices, largest error was 0.00000253955183
60 Correct 6 ms 376 KB used 1130 vertices, largest error was 0.00000321496801

Subtask #8
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000008111111
2 Correct 3 ms 380 KB used 390 vertices, largest error was 0.00000030199996
3 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000013533332
4 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000045889391
5 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000030199996
6 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000025999999
7 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000120199935
8 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012111111
9 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012111111
10 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000033092428
11 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000008442880
12 Correct 4 ms 376 KB used 430 vertices, largest error was 0.00000717898774
13 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000057650166
14 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
15 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
16 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000013150701
17 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004662742
18 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000006374210
19 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000006275000
20 Correct 13 ms 376 KB used 350 vertices, largest error was 0.00000011081120
21 Correct 4 ms 376 KB used 430 vertices, largest error was 0.00000108970434
22 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000012244342
23 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000025256908
24 Correct 4 ms 376 KB used 390 vertices, largest error was 0.00000054791554
25 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004234995
26 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000040731849
27 Correct 3 ms 376 KB used 350 vertices, largest error was 0.00000004738430
28 Correct 4 ms 376 KB used 350 vertices, largest error was 0.00000004683774
29 Correct 3 ms 376 KB used 390 vertices, largest error was 0.00000148940376
30 Correct 4 ms 376 KB used 390 vertices, largest error was 0.00000070293978
31 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000009951180
32 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000024648484
33 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000008454028
34 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000004662742
35 Correct 3 ms 256 KB used 266 vertices, largest error was 0.00000009938108
36 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000004662742
37 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000036020209
38 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000008501079
39 Correct 3 ms 376 KB used 286 vertices, largest error was 0.00000004662742
40 Correct 3 ms 376 KB used 266 vertices, largest error was 0.00000019841817
41 Correct 0 ms 376 KB used 160 vertices, largest error was 0.00000010553517
42 Correct 3 ms 376 KB used 180 vertices, largest error was 0.00000004307537
43 Correct 3 ms 376 KB used 180 vertices, largest error was 0.00000003252115
44 Correct 3 ms 376 KB used 200 vertices, largest error was 0.00000013351743
45 Correct 4 ms 256 KB used 220 vertices, largest error was 0.00000036628725
46 Correct 3 ms 256 KB used 180 vertices, largest error was 0.00000013056731
47 Correct 3 ms 376 KB used 220 vertices, largest error was 0.00000012402993
48 Correct 3 ms 376 KB used 200 vertices, largest error was 0.00000013676669
49 Correct 3 ms 376 KB used 180 vertices, largest error was 0.00000060296770
50 Correct 3 ms 376 KB used 180 vertices, largest error was 0.00000054043226
51 Correct 5 ms 376 KB used 722 vertices, largest error was 0.00000030454489
52 Correct 4 ms 376 KB used 474 vertices, largest error was 0.00000013837772
53 Correct 6 ms 376 KB used 990 vertices, largest error was 0.00000013451865
54 Correct 5 ms 376 KB used 742 vertices, largest error was 0.00000015254838
55 Correct 4 ms 376 KB used 578 vertices, largest error was 0.00000006707106
56 Correct 4 ms 376 KB used 494 vertices, largest error was 0.00000013877504
57 Correct 4 ms 376 KB used 474 vertices, largest error was 0.00000008819415
58 Correct 4 ms 376 KB used 494 vertices, largest error was 0.00000030033285
59 Correct 4 ms 368 KB used 474 vertices, largest error was 0.00000006932463
60 Correct 3 ms 376 KB used 722 vertices, largest error was 0.00000022018799
61 Correct 6 ms 376 KB used 1134 vertices, largest error was 0.00000008072091
62 Correct 6 ms 376 KB used 1150 vertices, largest error was 0.00000066405194
63 Correct 6 ms 372 KB used 842 vertices, largest error was 0.00000023500389
64 Correct 5 ms 376 KB used 842 vertices, largest error was 0.00000240827671
65 Correct 5 ms 376 KB used 926 vertices, largest error was 0.00000126282600
66 Correct 6 ms 376 KB used 1214 vertices, largest error was 0.00000200539773
67 Correct 6 ms 376 KB used 1070 vertices, largest error was 0.00000080974555
68 Correct 7 ms 376 KB used 1234 vertices, largest error was 0.00000037878823
69 Correct 6 ms 376 KB used 966 vertices, largest error was 0.00000253955183
70 Correct 6 ms 376 KB used 1130 vertices, largest error was 0.00000321496801
71 Correct 10 ms 400 KB used 1970 vertices, largest error was 0.00000025383841
72 Correct 8 ms 380 KB used 1594 vertices, largest error was 0.00000040839537
73 Correct 6 ms 448 KB used 1990 vertices, largest error was 0.00000044604177
74 Correct 8 ms 376 KB used 1636 vertices, largest error was 0.00000041598958
75 Correct 9 ms 376 KB used 1780 vertices, largest error was 0.00000122320325
76 Correct 9 ms 376 KB used 1822 vertices, largest error was 0.00000037285547
77 Correct 8 ms 376 KB used 1614 vertices, largest error was 0.00000032988119
78 Correct 6 ms 376 KB used 1990 vertices, largest error was 0.00000039167577
79 Correct 9 ms 248 KB used 2050 vertices, largest error was 0.00000051738933