QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#705208#1190. Twin Trees BrosTheZoneAC ✓89ms4404kbC++206.8kb2024-11-02 22:31:072024-11-02 22:31:08

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 22:31:08]
  • 评测
  • 测评结果:AC
  • 用时:89ms
  • 内存:4404kb
  • [2024-11-02 22:31:07]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <assert.h>
using namespace std;

const double eps = 1e-8;
int sgn(double a){return a<-eps?-1:a>eps?1:0;}
int sgn(double a, double b){return sgn(a-b);}
struct point{
    double x,y,z;
    point() {}
    point(double x,double y,double z): x(x), y(y), z(z) {}
    point operator+ (const point& p){
        return point(x+p.x, y+p.y, z+p.z);
    }
    point operator- (const point& p){
        return point(x-p.x, y-p.y, z-p.z);
    }
    point operator/ (const double d){
        return point(x/d, y/d, z/d);
    }
    double dist(const point& p){
        return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y) + (z-p.z)*(z-p.z));
    }
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    // input
    int n; cin >> n;
    vector<point> A(n);
    for(int i=0;i<n;i++){
        int x,y,z; cin >> x >> y >> z;
        A[i] = point(x,y,z);
    }
    vector<vector<int>> g1(n);
    for(int i=1;i<n;i++){
        int x,y; cin >> x >> y;
        x--; y--;
        g1[x].push_back(y);
        g1[y].push_back(x);
    }
    vector<point> B(n);
    for(int i=0;i<n;i++){
        int x,y,z; cin >> x >> y >> z;
        B[i] = point(x,y,z);
    }
    vector<vector<int>> g2(n);
    for(int i=1;i<n;i++){
        int x,y; cin >> x >> y;
        x -= n+1; y -= n+1;
        g2[x].push_back(y);
        g2[y].push_back(x);
    }

    // 木の葉ノードを基準に変形
    auto getTree = [&](vector<point> A, vector<vector<int>> &g, int leaf, int idx = -1)->vector<point>{
        // step1: 葉ノードを原点に平行移動させる
        {
            auto p = A[leaf];
            for(int i=0;i<n;i++){
                A[i] = A[i]-p;
            }
        }
        // step2: 葉ノードと親の距離を1にする
        int par = g[leaf][0];
        {
            double d = A[leaf].dist(A[par]);
            vector<point> nA(n);
            nA[leaf] = A[leaf];
            auto dfs = [&](auto self, int s, int p)->void{
                for(int t:g1[s]){
                    if(t == p) continue;
                    point v = (A[t]-A[s])/d;
                    nA[t] = nA[s]+v;
                    self(self, t, s);
                }
            };
            dfs(dfs, leaf, -1);
            swap(A, nA);
        }
        // step3:z軸中心に回転させ、親ノードをxz平面上へ
        {
            double theta = -atan2(A[par].y, A[par].x);
            for(int i=0;i<n;i++){
                double nx = A[i].x*cos(theta) - A[i].y*sin(theta);
                double ny = A[i].x*sin(theta) + A[i].y*cos(theta);
                A[i].x = nx, A[i].y = ny;
            }
        }
        // step4:y軸中心に回転させ、親ノードをx軸上へ
        {
            double theta = -atan2(A[par].z, A[par].x);
            for(int i=0;i<n;i++){
                double nx = A[i].x*cos(theta) - A[i].z*sin(theta);
                double nz = A[i].x*sin(theta) + A[i].z*cos(theta);
                A[i].x = nx, A[i].z = nz;
            }
        }
        // step5:x軸中心に回転させ、親ノードに接続する元の葉以外をy軸上へ
        // idx = -1 ならば任意、それ以外はA[idx]を合わせる
        if(idx == -1){
            for(int t:g[par]){
                if(t == leaf) continue;
                if(abs(A[t].y) < eps and abs(A[t].z) < eps) continue;
                idx = t; break;
            }
        }
        if(idx != -1){
            double theta = -atan2(A[idx].z, A[idx].y);
            for(int i=0;i<n;i++){
                double ny = A[i].y*cos(theta) - A[i].z*sin(theta);
                double nz = A[i].y*sin(theta) + A[i].z*cos(theta);
                A[i].y = ny, A[i].z = nz;
            }
        }
        return A;
    };

    int lA = -1;
    for(int i=0;i<n;i++){
        sort(g1[i].begin(), g1[i].end());
        if(g1[i].size() == 1) lA = i;
    }
    assert(lA != -1);
    auto gA = getTree(A, g1, lA);

    // 比較用の関数
    set<vector<int>> st;
    auto compare = [&](vector<point> &A, vector<point> &B)->void{
        vector<int> Bidx(n,-1),Binv(n);
        // A[i] = B[Bidx[i]]
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(sgn(A[i].x, B[j].x) or sgn(A[i].y, B[j].y) or sgn(A[i].z, B[j].z)) continue;
                Bidx[i] = j; Binv[j] = i; break;
            }
            if(Bidx[i] == -1) return;
        }
        // 隣接リストがそれぞれ一致しているか調べる
        for(int i=0;i<n;i++){
            auto v = g1[i], vv = g2[Bidx[i]];
            for(int &j:vv){
                j = Binv[j];
            }
            sort(vv.begin(), vv.end());
            if(v != vv) return;
        }
        st.insert(Bidx);
    };

    // AとBの比較
    for(int i=0;i<n;i++){
        if(g2[i].size() != 1) continue;
        // iは葉ノード
        int par = g2[i][0];
        // step5でy軸に合わせるidxを全て試す
        for(int j:g2[par]){
            auto gB = getTree(B, g2, i, (i==j?-1:j));
            compare(gA, gB);
        }
    }

    // output
    cout << st.size() << endl;
}


























































































































































































































































































































































































































































































































































































































































































































































































































































Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4164kb

input:

3
0 0 0
1 0 0
3 0 0
1 2
2 3
0 0 0
0 2 2
0 3 3
4 5
5 6

output:

1

result:

ok answer is '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4104kb

input:

4
1 0 0
2 0 0
2 1 0
2 -1 0
1 2
2 3
2 4
0 1 1
0 0 0
0 2 0
0 0 2
5 6
5 7
5 8

output:

2

result:

ok answer is '2'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4300kb

input:

3
0 0 0
1 0 0
3 0 0
1 2
2 3
0 0 0
0 2 2
0 3 3
4 5
5 6

output:

1

result:

ok answer is '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 4076kb

input:

7
5 3 1
5 5 3
5 1 -1
7 5 3
3 5 3
7 1 -1
3 1 -1
1 2
1 3
1 4
1 5
1 6
1 7
13 23 24
10 20 30
10 20 36
10 20 24
13 23 36
7 17 36
7 17 24
8 9
9 10
9 11
9 12
9 13
9 14

output:

4

result:

ok answer is '4'

Test #5:

score: 0
Accepted
time: 0ms
memory: 4244kb

input:

7
5 3 1
5 5 3
5 1 -1
7 5 3
3 5 3
7 1 -1
3 1 -1
1 2
1 3
1 4
1 5
1 6
1 7
13 23 24
13 23 36
10 20 30
10 20 36
10 20 24
7 17 36
7 17 24
8 9
9 10
10 11
10 12
10 13
10 14

output:

0

result:

ok answer is '0'

Test #6:

score: 0
Accepted
time: 0ms
memory: 4096kb

input:

7
5 3 1
5 5 3
5 1 -1
7 5 3
3 5 3
7 1 -1
3 1 -1
1 2
1 3
1 4
1 5
1 6
1 7
13 23 24
10 20 30
10 20 36
10 20 24
13 23 37
7 17 36
7 17 24
8 9
9 10
9 11
9 12
9 13
9 14

output:

0

result:

ok answer is '0'

Test #7:

score: 0
Accepted
time: 0ms
memory: 4152kb

input:

9
134 234 164
185 285 198
134 234 232
185 285 266
134 234 300
185 285 334
134 234 368
185 285 402
134 234 436
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
50 30 278
184 164 680
-84 -104 680
318 298 278
-218 -238 278
452 432 680
-352 -372 680
586 566 278
-486 -506 278
10 11
10 12
11 13
12 14
13 15
14 16
15 17
16 18

output:

2

result:

ok answer is '2'

Test #8:

score: 0
Accepted
time: 0ms
memory: 4156kb

input:

9
185 285 198
134 234 436
185 285 266
185 285 402
134 234 232
134 234 300
134 234 368
134 234 164
185 285 334
1 8
1 5
2 4
3 5
3 6
4 7
6 9
7 9
318 298 278
452 432 680
184 164 680
-218 -238 278
-352 -372 680
586 566 278
-486 -506 278
-84 -104 680
50 30 278
10 12
10 11
11 15
12 18
13 17
13 14
14 16
17 18

output:

2

result:

ok answer is '2'

Test #9:

score: 0
Accepted
time: 0ms
memory: 4084kb

input:

9
185 285 198
134 234 436
185 285 266
185 285 402
134 234 232
134 234 300
134 234 368
134 234 164
185 285 334
1 8
1 5
2 6
3 5
3 6
4 7
6 9
7 9
318 298 278
452 432 680
184 164 680
-218 -238 278
-352 -372 680
586 566 278
-486 -506 278
-84 -104 680
50 30 278
10 12
10 11
11 15
12 18
13 17
13 14
14 16
17 18

output:

0

result:

ok answer is '0'

Test #10:

score: 0
Accepted
time: 0ms
memory: 4156kb

input:

9
185 285 198
134 235 436
185 285 266
185 285 402
134 234 232
134 234 300
134 234 368
134 234 164
185 285 334
1 8
1 5
2 4
3 5
3 6
4 7
6 9
7 9
318 298 278
452 432 680
184 164 680
-218 -238 278
-352 -372 680
586 566 278
-486 -506 278
-84 -104 680
50 30 278
10 12
10 11
11 15
12 18
13 17
13 14
14 16
17 18

output:

0

result:

ok answer is '0'

Test #11:

score: 0
Accepted
time: 0ms
memory: 4004kb

input:

7
-220 520 720
60 240 440
200 100 300
620 -320 -120
-80 380 580
480 -180 20
340 -40 160
1 3
1 7
1 6
1 4
2 3
3 5
230 210 370
50 30 10
170 150 250
-10 -30 -110
-130 -150 -350
110 90 130
-70 -90 -230
8 11
8 9
8 14
8 12
9 10
9 13

output:

1

result:

ok answer is '1'

Test #12:

score: 0
Accepted
time: 0ms
memory: 4004kb

input:

7
-220 520 720
60 240 440
200 100 300
620 -320 -120
-80 380 580
480 -180 20
340 -40 160
1 3
1 7
1 6
2 3
3 5
4 5
230 210 370
50 30 10
170 150 250
-10 -30 -110
-130 -150 -350
110 90 130
-70 -90 -230
8 11
8 9
8 14
8 12
9 10
9 13

output:

0

result:

ok answer is '0'

Test #13:

score: 0
Accepted
time: 0ms
memory: 4232kb

input:

7
-220 520 720
60 240 440
200 100 300
620 -320 -120
-80 380 580
480 -180 20
341 -40 161
1 3
1 7
1 6
1 4
2 3
3 5
230 210 370
50 30 10
170 150 250
-10 -30 -110
-130 -150 -350
110 90 130
-70 -90 -230
8 11
8 9
8 14
8 12
9 10
9 13

output:

0

result:

ok answer is '0'

Test #14:

score: 0
Accepted
time: 0ms
memory: 4232kb

input:

12
-356 -256 92
-356 -256 -12
-356 -256 612
-252 -152 612
-252 -152 508
-252 -152 92
-356 -256 508
-252 -152 196
-252 -152 -12
-252 -152 404
-356 -256 404
-356 -256 196
1 4
2 4
3 11
4 5
4 12
5 11
6 12
7 11
8 12
9 12
10 11
602 582 194
234 214 562
418 398 562
-134 -154 562
234 214 194
-134 -154 194
-3...

output:

1

result:

ok answer is '1'

Test #15:

score: 0
Accepted
time: 0ms
memory: 4164kb

input:

12
-356 -256 92
-356 -256 -12
-356 -256 612
-252 -152 612
-252 -152 508
-252 -152 92
-356 -256 508
-252 -152 196
-252 -152 -12
-252 -152 404
-356 -256 404
-356 -256 196
1 4
2 4
3 11
4 5
4 12
5 11
6 7
7 11
8 12
9 12
10 11
602 582 194
234 214 562
418 398 562
-134 -154 562
234 214 194
-134 -154 194
-31...

output:

0

result:

ok answer is '0'

Test #16:

score: 0
Accepted
time: 0ms
memory: 4096kb

input:

12
-356 -256 92
-356 -256 -12
-356 -256 612
-252 -152 612
-252 -152 508
-252 -152 93
-356 -256 508
-252 -152 196
-252 -152 -12
-252 -152 404
-356 -256 404
-356 -256 196
1 4
2 4
3 11
4 5
4 12
5 11
6 12
7 11
8 12
9 12
10 11
418 398 562
-502 -522 562
-134 -154 194
234 214 562
-502 -522 194
602 582 562
...

output:

0

result:

ok answer is '0'

Test #17:

score: 0
Accepted
time: 0ms
memory: 4008kb

input:

4
-500 -400 360
-500 -400 240
100 200 240
100 200 360
1 2
2 4
3 4
890 114 94
-790 114 94
890 -54 -74
-790 -54 -74
5 8
5 7
6 8

output:

2

result:

ok answer is '2'

Test #18:

score: 0
Accepted
time: 0ms
memory: 4032kb

input:

4
-500 -400 360
-500 -400 240
100 200 240
100 200 360
1 2
2 4
3 4
890 114 94
890 -54 -74
-790 114 94
-790 -54 -74
5 8
6 7
7 8

output:

0

result:

ok answer is '0'

Test #19:

score: 0
Accepted
time: 0ms
memory: 4100kb

input:

4
-500 -400 360
-500 -400 240
100 200 240
100 200 360
1 2
2 4
3 4
-790 114 94
890 -54 -75
890 114 94
-790 -54 -74
5 8
6 7
7 8

output:

0

result:

ok answer is '0'

Test #20:

score: 0
Accepted
time: 0ms
memory: 4008kb

input:

4
1 0 0
2 0 0
2 1 0
2 -1 0
1 2
2 3
2 4
0 1 1
0 0 0
0 2 0
0 0 2
5 6
5 7
5 8

output:

2

result:

ok answer is '2'

Test #21:

score: 0
Accepted
time: 3ms
memory: 4300kb

input:

199
-175 -10 195
-95 -125 390
-110 25 310
-105 -170 360
-145 -60 205
-340 -75 315
-305 -10 275
-245 -5 230
-175 5 390
-295 -40 230
-235 -90 205
-290 -225 310
-130 -5 360
-105 -45 260
-95 -190 275
-105 -30 345
-240 -5 355
-90 -15 365
-295 -155 260
-285 -165 410
-245 -195 370
-225 -115 160
-235 -195 2...

output:

24

result:

ok answer is '24'

Test #22:

score: 0
Accepted
time: 2ms
memory: 4156kb

input:

199
-175 -10 195
-95 -125 390
-110 25 310
-105 -170 360
-145 -60 205
-340 -75 315
-305 -10 275
-245 -5 230
-175 5 390
-295 -40 230
-235 -90 205
-290 -225 310
-130 -5 360
-105 -45 260
-95 -190 275
-105 -30 345
-240 -5 355
-90 -15 365
-295 -155 260
-285 -165 410
-245 -195 370
-225 -115 160
-235 -195 2...

output:

0

result:

ok answer is '0'

Test #23:

score: 0
Accepted
time: 2ms
memory: 4284kb

input:

199
-175 -10 195
-95 -125 390
-110 25 310
-105 -170 360
-145 -60 205
-340 -75 315
-305 -10 275
-245 -5 230
-175 5 390
-295 -40 230
-235 -90 205
-290 -225 310
-130 -5 360
-105 -45 260
-95 -190 275
-105 -30 345
-240 -5 355
-90 -15 365
-295 -155 260
-285 -165 410
-245 -195 370
-225 -115 160
-235 -195 2...

output:

0

result:

ok answer is '0'

Test #24:

score: 0
Accepted
time: 1ms
memory: 4152kb

input:

165
-170 -94 357
-221 -121 384
-191 -55 294
-143 -139 309
-158 -106 351
-161 -184 267
-146 -178 282
-209 -43 339
-158 -181 264
-149 -157 285
-179 -184 321
-215 -151 357
-209 -55 306
-239 -16 267
-185 -43 249
-221 -16 321
-209 -145 294
-233 -16 339
-248 -148 213
-194 -70 243
-242 -19 264
-179 -16 279...

output:

8

result:

ok answer is '8'

Test #25:

score: 0
Accepted
time: 1ms
memory: 4092kb

input:

165
-170 -94 357
-221 -121 384
-191 -55 294
-143 -139 309
-158 -106 351
-161 -184 267
-146 -178 282
-209 -43 339
-158 -181 264
-149 -157 285
-179 -184 321
-215 -151 357
-209 -55 306
-239 -16 267
-185 -43 249
-221 -16 321
-209 -145 294
-233 -16 339
-248 -148 213
-194 -70 243
-242 -19 264
-179 -16 279...

output:

0

result:

ok answer is '0'

Test #26:

score: 0
Accepted
time: 1ms
memory: 4116kb

input:

165
-170 -94 357
-221 -121 384
-191 -55 294
-143 -139 309
-158 -106 351
-161 -184 267
-146 -178 282
-209 -43 339
-158 -181 264
-149 -157 285
-179 -184 321
-215 -151 357
-209 -55 306
-239 -16 267
-185 -43 249
-221 -16 321
-209 -145 294
-233 -16 339
-248 -148 213
-194 -70 243
-242 -19 264
-179 -16 279...

output:

0

result:

ok answer is '0'

Test #27:

score: 0
Accepted
time: 1ms
memory: 4404kb

input:

165
-248 -58 384
-221 -139 261
-239 -121 261
-116 -58 348
-239 -88 234
-239 -106 345
-125 -151 279
-230 -121 339
-146 -55 285
-149 -109 249
-221 -61 339
-179 -49 225
-239 -115 333
-254 -85 255
-239 -133 285
-284 -148 258
-167 -115 339
-251 -49 291
-170 -121 261
-248 -142 216
-245 -94 339
-266 -112 2...

output:

4

result:

ok answer is '4'

Test #28:

score: 0
Accepted
time: 1ms
memory: 4140kb

input:

165
-248 -58 384
-221 -139 261
-239 -121 261
-116 -58 348
-239 -88 234
-239 -106 345
-125 -151 279
-230 -121 339
-146 -55 285
-149 -109 249
-221 -61 339
-179 -49 225
-239 -115 333
-254 -85 255
-239 -133 285
-284 -148 258
-167 -115 339
-251 -49 291
-170 -121 261
-248 -142 216
-245 -94 339
-266 -112 2...

output:

0

result:

ok answer is '0'

Test #29:

score: 0
Accepted
time: 1ms
memory: 4148kb

input:

165
-248 -58 384
-221 -139 261
-239 -121 261
-116 -58 348
-239 -88 234
-239 -106 345
-125 -151 279
-230 -121 339
-146 -55 285
-149 -109 249
-221 -61 339
-179 -49 225
-239 -115 333
-254 -85 255
-239 -133 285
-284 -148 258
-167 -115 339
-251 -49 291
-170 -121 261
-248 -142 216
-245 -94 339
-266 -112 2...

output:

0

result:

ok answer is '0'

Test #30:

score: 0
Accepted
time: 0ms
memory: 4024kb

input:

67
-39 -16 321
-277 -142 307
-39 -121 384
-396 -30 405
-312 -219 272
-4 -30 195
-361 -16 279
-270 -100 300
-305 5 328
-95 5 272
-361 -121 216
-95 -128 195
-88 19 272
-396 -170 195
-116 -184 412
-361 -79 384
-88 -79 384
-95 -72 405
-116 -16 188
-130 -100 300
-361 -184 321
-312 19 328
-312 -184 279
-4...

output:

8

result:

ok answer is '8'

Test #31:

score: 0
Accepted
time: 1ms
memory: 4016kb

input:

67
-39 -16 321
-277 -142 307
-39 -121 384
-396 -30 405
-312 -219 272
-4 -30 195
-361 -16 279
-270 -100 300
-305 5 328
-95 5 272
-361 -121 216
-95 -128 195
-88 19 272
-396 -170 195
-116 -184 412
-361 -79 384
-88 -79 384
-95 -72 405
-116 -16 188
-130 -100 300
-361 -184 321
-312 19 328
-312 -184 279
-4...

output:

0

result:

ok answer is '0'

Test #32:

score: 0
Accepted
time: 1ms
memory: 4052kb

input:

67
-39 -16 321
-277 -142 307
-39 -121 384
-396 -30 405
-312 -219 272
-4 -30 195
-361 -16 279
-270 -100 300
-305 5 328
-95 5 272
-361 -121 216
-95 -128 195
-88 19 272
-396 -170 195
-116 -184 412
-361 -79 384
-88 -79 384
-95 -72 405
-116 -16 188
-130 -100 300
-361 -184 321
-312 19 328
-312 -184 279
-4...

output:

0

result:

ok answer is '0'

Test #33:

score: 0
Accepted
time: 1ms
memory: 4176kb

input:

83
-81 -51 125
-242 -191 181
-123 -128 391
-109 -219 125
-326 -198 503
-81 -191 475
-277 -79 146
-144 26 426
-291 -142 419
-109 -58 419
-165 -191 97
-109 -135 503
-123 -121 146
-81 -149 475
-277 -121 454
-193 -135 216
-81 -9 125
-193 -65 384
-249 19 125
-109 -65 97
-291 -219 475
-235 -191 503
-123 -...

output:

2

result:

ok answer is '2'

Test #34:

score: 0
Accepted
time: 0ms
memory: 4252kb

input:

83
-81 -51 125
-242 -191 181
-123 -128 391
-109 -219 125
-326 -198 503
-81 -191 475
-277 -79 146
-144 26 426
-291 -142 419
-109 -58 419
-165 -191 97
-109 -135 503
-123 -121 146
-81 -149 475
-277 -121 454
-193 -135 216
-81 -9 125
-193 -65 384
-249 19 125
-109 -65 97
-291 -219 475
-235 -191 503
-123 -...

output:

0

result:

ok answer is '0'

Test #35:

score: 0
Accepted
time: 0ms
memory: 4028kb

input:

83
-81 -51 125
-242 -191 181
-123 -128 391
-109 -219 125
-326 -198 503
-81 -191 475
-277 -79 146
-144 26 426
-291 -142 419
-109 -58 419
-165 -191 97
-109 -135 503
-123 -121 146
-81 -149 475
-277 -121 454
-193 -135 216
-81 -9 125
-193 -65 384
-249 19 125
-109 -65 97
-291 -219 475
-235 -191 503
-123 -...

output:

0

result:

ok answer is '0'

Test #36:

score: 0
Accepted
time: 1ms
memory: 4180kb

input:

83
-102 -142 321
-81 -156 167
-298 -142 279
-102 -163 174
3 -65 174
-326 -44 195
-123 -198 216
-291 19 286
-109 -114 419
-81 33 244
3 -226 265
-354 -16 265
-123 -2 384
-403 -135 174
-277 -16 398
-74 -156 195
3 26 335
-319 -233 244
-277 -198 384
-81 -44 433
-102 26 237
-74 -205 356
-46 -121 321
-291 ...

output:

2

result:

ok answer is '2'

Test #37:

score: 0
Accepted
time: 1ms
memory: 4180kb

input:

83
-102 -142 321
-81 -156 167
-298 -142 279
-102 -163 174
3 -65 174
-326 -44 195
-123 -198 216
-291 19 286
-109 -114 419
-81 33 244
3 -226 265
-354 -16 265
-123 -2 384
-403 -135 174
-277 -16 398
-74 -156 195
3 26 335
-319 -233 244
-277 -198 384
-81 -44 433
-102 26 237
-74 -205 356
-46 -121 321
-291 ...

output:

0

result:

ok answer is '0'

Test #38:

score: 0
Accepted
time: 1ms
memory: 4100kb

input:

83
-102 -142 321
-81 -156 167
-298 -142 279
-102 -163 174
3 -65 174
-326 -44 195
-123 -198 216
-291 19 286
-109 -114 419
-81 33 244
3 -226 265
-354 -16 265
-123 -2 384
-403 -135 174
-277 -16 398
-74 -156 195
3 26 335
-319 -233 244
-277 -198 384
-81 -44 433
-102 26 237
-74 -205 356
-46 -121 321
-291 ...

output:

0

result:

ok answer is '0'

Test #39:

score: 0
Accepted
time: 0ms
memory: 4172kb

input:

83
-92 50 106
-4 82 -34
96 -70 66
92 -82 -14
56 50 102
40 -26 82
-8 66 10
24 -70 98
44 82 46
92 62 74
52 50 -46
24 58 90
-40 66 18
52 -70 -22
-64 102 -42
32 50 14
-80 62 82
24 -78 -30
56 10 18
-84 82 14
40 42 46
32 62 90
24 102 102
-52 98 -22
48 14 102
40 62 -22
-4 50 82
16 106 -30
-88 34 90
20 -10 ...

output:

2

result:

ok answer is '2'

Test #40:

score: 0
Accepted
time: 1ms
memory: 4108kb

input:

83
-92 50 106
-4 82 -34
96 -70 66
92 -82 -14
56 50 102
40 -26 82
-8 66 10
24 -70 98
44 82 46
92 62 74
52 50 -46
24 58 90
-40 66 18
52 -70 -22
-64 102 -42
32 50 14
-80 62 82
24 -78 -30
56 10 18
-84 82 14
40 42 46
32 62 90
24 102 102
-52 98 -22
48 14 102
40 62 -22
-4 50 82
16 106 -30
-88 34 90
20 -10 ...

output:

0

result:

ok answer is '0'

Test #41:

score: 0
Accepted
time: 1ms
memory: 4124kb

input:

83
-92 50 106
-4 82 -34
96 -70 66
92 -82 -14
56 50 102
40 -26 82
-8 66 10
24 -70 98
44 82 46
92 62 74
52 50 -46
24 58 90
-40 66 18
52 -70 -22
-64 102 -42
32 50 14
-80 62 82
24 -78 -30
56 10 18
-84 82 14
40 42 46
32 62 90
24 102 102
-52 98 -22
48 14 102
40 62 -22
-4 50 82
16 106 -30
-88 34 90
20 -10 ...

output:

0

result:

ok answer is '0'

Test #42:

score: 0
Accepted
time: 0ms
memory: 4288kb

input:

200
139 5 8
-17 5 8
231 5 8
135 5 8
-201 5 8
-377 5 8
79 5 8
123 5 8
235 5 8
-57 5 8
-225 5 8
-361 5 8
-161 5 8
-373 5 8
-129 5 8
23 5 8
-177 5 8
-65 5 8
-77 5 8
-353 5 8
267 5 8
-69 5 8
147 5 8
227 5 8
351 5 8
-305 5 8
-1 5 8
-165 5 8
55 5 8
-257 5 8
263 5 8
-121 5 8
-221 5 8
-249 5 8
159 5 8
67 5 ...

output:

1

result:

ok answer is '1'

Test #43:

score: 0
Accepted
time: 2ms
memory: 4292kb

input:

200
139 5 8
-17 5 8
231 5 8
135 5 8
-201 5 8
-377 5 8
79 5 8
123 5 8
235 5 8
-57 5 8
-225 5 8
-361 5 8
-161 5 8
-373 5 8
-129 5 8
23 5 8
-177 5 8
-65 5 8
-77 5 8
-353 5 8
267 5 8
-69 5 8
147 5 8
227 5 8
351 5 8
-305 5 8
-1 5 8
-165 5 8
55 5 8
-257 5 8
263 5 8
-121 5 8
-221 5 8
-249 5 8
159 5 8
67 5 ...

output:

0

result:

ok answer is '0'

Test #44:

score: 0
Accepted
time: 1ms
memory: 4280kb

input:

200
139 5 8
-17 5 8
231 5 8
135 5 8
-201 5 8
-377 5 8
79 5 8
123 5 8
235 5 8
-57 5 8
-225 5 8
-361 5 8
-161 5 8
-373 5 8
-129 5 8
23 5 8
-177 5 8
-65 5 8
-77 5 8
-353 5 8
267 5 8
-69 5 8
147 5 8
227 5 8
351 5 8
-305 5 8
-1 5 8
-165 5 8
55 5 8
-257 5 8
263 5 8
-121 5 8
-221 5 8
-249 5 8
159 5 8
67 5 ...

output:

0

result:

ok answer is '0'

Test #45:

score: 0
Accepted
time: 0ms
memory: 4348kb

input:

200
105 73 42
-12 -5 3
174 119 65
102 71 41
-150 -97 -43
-282 -185 -87
60 43 27
93 65 38
177 121 66
-42 -25 -7
-168 -109 -49
-270 -177 -83
-120 -77 -33
-279 -183 -86
-96 -61 -25
18 15 13
-132 -85 -37
-48 -29 -9
-57 -35 -12
-264 -173 -81
201 137 74
-51 -31 -10
111 77 44
171 117 64
264 179 95
-228 -14...

output:

1

result:

ok answer is '1'

Test #46:

score: 0
Accepted
time: 0ms
memory: 4028kb

input:

200
105 73 42
-12 -5 3
174 119 65
102 71 41
-150 -97 -43
-282 -185 -87
60 43 27
93 65 38
177 121 66
-42 -25 -7
-168 -109 -49
-270 -177 -83
-120 -77 -33
-279 -183 -86
-96 -61 -25
18 15 13
-132 -85 -37
-48 -29 -9
-57 -35 -12
-264 -173 -81
201 137 74
-51 -31 -10
111 77 44
171 117 64
264 179 95
-228 -14...

output:

0

result:

ok answer is '0'

Test #47:

score: 0
Accepted
time: 1ms
memory: 4032kb

input:

200
105 73 42
-12 -5 3
174 119 65
102 71 41
-150 -97 -43
-282 -185 -87
60 43 27
93 65 38
177 121 66
-42 -25 -7
-168 -109 -49
-270 -177 -83
-120 -77 -33
-279 -183 -86
-96 -61 -25
18 15 13
-132 -85 -37
-48 -29 -9
-57 -35 -12
-264 -173 -81
201 137 74
-51 -31 -10
111 77 44
171 117 64
264 179 95
-228 -14...

output:

0

result:

ok answer is '0'

Test #48:

score: 0
Accepted
time: 89ms
memory: 4136kb

input:

200
-473 -322 -77
-13 618 479
-49 670 -221
85 -450 477
11 -136 39
49 48 -537
-687 14 -155
-289 176 399
213 -268 -263
19 2 -19
-23 -484 -137
451 -194 281
-509 264 -195
205 -48 571
-407 -310 -311
435 -354 -267
303 188 211
309 418 327
19 -366 541
-97 276 619
291 -240 -531
-583 248 -387
339 272 481
-145...

output:

1

result:

ok answer is '1'

Test #49:

score: 0
Accepted
time: 83ms
memory: 4140kb

input:

200
-473 -322 -77
463 -444 545
-49 670 -221
85 -450 477
-653 206 -343
49 48 -537
-303 -368 525
-289 176 399
213 -268 -263
19 2 -19
-23 -484 -137
451 -194 281
-509 264 -195
205 -48 571
-407 -310 -311
225 292 -483
-157 -446 139
481 -272 527
19 -366 541
-97 276 619
291 -240 -531
-583 248 -387
339 272 4...

output:

0

result:

ok answer is '0'

Test #50:

score: 0
Accepted
time: 84ms
memory: 4052kb

input:

200
-473 -322 -77
-13 618 479
-49 670 -221
85 -450 477
11 -136 39
49 48 -537
-687 14 -155
-289 176 399
213 -268 -263
19 2 -19
-23 -484 -137
451 -194 281
-509 264 -195
205 -48 571
-407 -310 -311
435 -354 -267
303 188 211
309 418 327
19 -366 541
-97 276 619
291 -240 -531
-583 248 -387
339 272 481
-145...

output:

0

result:

ok answer is '0'

Test #51:

score: 0
Accepted
time: 87ms
memory: 4132kb

input:

200
387 5 8
35 5 8
-73 5 8
-353 5 8
-261 5 8
-61 5 8
-125 5 8
211 5 8
127 5 8
-237 5 8
99 5 8
-209 5 8
255 5 8
-137 5 8
347 5 8
-213 5 8
-97 5 8
187 5 8
-105 5 8
3 5 8
-113 5 8
-89 5 8
215 5 8
-249 5 8
243 5 8
-129 5 8
-93 5 8
319 5 8
-221 5 8
-201 5 8
-225 5 8
139 5 8
19 5 8
-1 5 8
-277 5 8
363 5 8...

output:

1

result:

ok answer is '1'

Test #52:

score: 0
Accepted
time: 82ms
memory: 4140kb

input:

200
387 5 8
35 5 8
-73 5 8
-353 5 8
-261 5 8
-61 5 8
-125 5 8
211 5 8
127 5 8
-237 5 8
99 5 8
-209 5 8
255 5 8
-137 5 8
347 5 8
-213 5 8
-97 5 8
187 5 8
-105 5 8
3 5 8
-113 5 8
-89 5 8
215 5 8
-249 5 8
243 5 8
-129 5 8
-93 5 8
319 5 8
-221 5 8
-201 5 8
-225 5 8
139 5 8
19 5 8
-1 5 8
-277 5 8
363 5 8...

output:

0

result:

ok answer is '0'

Test #53:

score: 0
Accepted
time: 84ms
memory: 4060kb

input:

200
387 5 8
35 5 8
-73 5 8
-353 5 8
-261 5 8
-61 5 8
-125 5 8
211 5 8
127 5 8
-237 5 8
99 5 8
-209 5 8
255 5 8
-137 5 8
347 5 8
-213 5 8
-97 5 8
187 5 8
-105 5 8
3 5 8
-113 5 8
-89 5 8
215 5 8
-249 5 8
243 5 8
-129 5 8
-93 5 8
319 5 8
-221 5 8
-201 5 8
-225 5 8
139 5 8
19 5 8
-1 5 8
-277 5 8
363 5 8...

output:

0

result:

ok answer is '0'

Test #54:

score: 0
Accepted
time: 86ms
memory: 4088kb

input:

200
291 197 104
27 21 16
-54 -33 -11
-264 -173 -81
-195 -127 -58
-45 -27 -8
-93 -59 -24
159 109 60
96 67 39
-177 -115 -52
75 53 32
-156 -101 -45
192 131 71
-102 -65 -27
261 177 94
-159 -103 -46
-72 -45 -17
141 97 54
-78 -49 -19
3 5 8
-84 -53 -21
-66 -41 -15
162 111 61
-186 -121 -55
183 125 68
-96 -6...

output:

1

result:

ok answer is '1'

Test #55:

score: 0
Accepted
time: 82ms
memory: 4132kb

input:

200
291 197 104
27 21 16
-54 -33 -11
-264 -173 -81
-195 -127 -58
-45 -27 -8
-93 -59 -24
159 109 60
96 67 39
-177 -115 -52
75 53 32
-156 -101 -45
192 131 71
-102 -65 -27
261 177 94
-159 -103 -46
-72 -45 -17
141 97 54
-78 -49 -19
3 5 8
-84 -53 -21
-66 -41 -15
162 111 61
-186 -121 -55
183 125 68
-96 -6...

output:

0

result:

ok answer is '0'

Test #56:

score: 0
Accepted
time: 84ms
memory: 4216kb

input:

200
291 197 104
27 21 16
-54 -33 -11
-264 -173 -81
-195 -127 -58
-45 -27 -8
-93 -59 -24
159 109 60
96 67 39
-177 -115 -52
75 53 32
-156 -101 -45
192 131 71
-102 -65 -27
261 177 94
-159 -103 -46
-72 -45 -17
141 97 54
-78 -49 -19
3 5 8
-84 -53 -21
-66 -41 -15
162 111 61
-186 -121 -55
183 125 68
-96 -6...

output:

0

result:

ok answer is '0'

Test #57:

score: 0
Accepted
time: 0ms
memory: 4240kb

input:

4
1 0 0
2 0 0
2 1 0
2 -1 0
1 2
1 3
2 4
0 1 1
0 0 0
0 2 0
0 0 2
5 6
5 7
5 8

output:

0

result:

ok answer is '0'

Test #58:

score: 0
Accepted
time: 2ms
memory: 4088kb

input:

200
-200 -520 192
-216 -610 -266
-428 46 -248
30 92 -36
-558 -534 332
138 -42 -412
240 286 46
-196 -140 -32
408 -120 -544
-236 -434 24
534 276 596
-432 -68 -406
80 -294 442
160 174 -176
330 188 180
472 -390 -352
574 422 224
292 -264 -360
-156 340 -384
498 -156 580
500 354 -494
444 -32 540
-102 298 1...

output:

1

result:

ok answer is '1'

Test #59:

score: 0
Accepted
time: 1ms
memory: 4352kb

input:

200
-380 -610 462
-396 -700 4
-608 -44 22
-150 2 234
-738 -624 602
-42 -132 -142
60 196 316
-376 -230 238
228 -210 -274
-416 -524 294
354 186 866
-612 -158 -136
-100 -384 712
-20 84 94
150 98 450
292 -480 -82
394 332 494
112 -354 -90
-336 250 -114
318 -246 850
320 264 -224
264 -122 810
-282 208 286
...

output:

0

result:

ok answer is '0'

Test #60:

score: 0
Accepted
time: 1ms
memory: 4052kb

input:

200
-380 -610 462
-396 -700 4
-608 -44 22
-150 2 234
-738 -624 602
-42 -132 -142
60 196 316
-376 -230 238
228 -210 -274
-416 -524 294
354 186 866
-612 -158 -136
-100 -384 712
-20 84 94
150 98 450
292 -480 -82
394 332 494
112 -354 -90
-336 250 -114
318 -246 850
320 264 -224
264 -122 810
-282 208 286
...

output:

0

result:

ok answer is '0'

Test #61:

score: 0
Accepted
time: 2ms
memory: 4128kb

input:

200
-917 -637 399
574 -697 354
-614 626 807
556 866 -117
418 -775 852
439 122 -45
-644 512 150
658 -706 -816
97 -844 768
433 -784 -285
-14 620 486
649 -553 -159
499 482 546
-668 -46 -570
754 398 891
607 68 30
781 815 39
-515 -184 -417
118 -586 801
427 119 -153
37 482 297
-476 -190 -504
178 791 468
-...

output:

1

result:

ok answer is '1'

Test #62:

score: 0
Accepted
time: 0ms
memory: 4024kb

input:

200
-917 -637 399
574 -697 354
-614 626 807
556 866 -117
418 -775 852
439 122 -45
-644 512 150
658 -706 -816
97 -844 768
433 -784 -285
-14 620 486
649 -553 -159
499 482 546
-668 -46 -570
754 398 891
607 68 30
781 815 39
-515 -184 -417
118 -586 801
427 119 -153
37 482 297
-476 -190 -504
178 791 468
-...

output:

0

result:

ok answer is '0'

Test #63:

score: 0
Accepted
time: 2ms
memory: 4152kb

input:

200
-917 -637 399
574 -697 354
-614 626 807
556 866 -117
418 -775 852
439 122 -45
-644 512 150
658 -706 -816
97 -844 768
433 -784 -285
-14 620 486
649 -553 -159
499 482 546
-668 -46 -570
754 398 891
607 68 30
781 815 39
-515 -184 -417
118 -586 801
427 119 -153
37 482 297
-476 -190 -504
178 791 468
-...

output:

0

result:

ok answer is '0'

Test #64:

score: 0
Accepted
time: 2ms
memory: 4356kb

input:

200
160 -268 -288
28 588 548
180 -600 296
6 340 -66
10 56 -322
618 -372 130
-566 -38 -510
40 -498 -2
-336 -412 188
-548 -286 -550
-20 -110 -98
6 318 180
-372 276 -114
392 -98 402
602 272 -30
268 -12 542
-210 -322 374
270 -558 244
-28 202 562
148 -458 494
-420 -42 188
-236 -278 -160
-110 -424 418
514...

output:

1

result:

ok answer is '1'

Test #65:

score: 0
Accepted
time: 2ms
memory: 4292kb

input:

200
160 -268 -288
28 588 548
180 -600 296
6 340 -66
10 56 -322
618 -372 130
-566 -38 -510
40 -498 -2
-336 -412 188
-548 -286 -550
-20 -110 -98
6 318 180
-372 276 -114
392 -98 402
602 272 -30
268 -12 542
-210 -322 374
270 -558 244
-28 202 562
148 -458 494
-420 -42 188
-236 -278 -160
-110 -424 418
514...

output:

0

result:

ok answer is '0'

Test #66:

score: 0
Accepted
time: 0ms
memory: 4152kb

input:

200
160 -268 -288
28 588 548
180 -600 296
6 340 -66
10 56 -322
618 -372 130
-566 -38 -510
40 -498 -2
-336 -412 188
-548 -286 -550
-20 -110 -98
6 318 180
-372 276 -114
392 -98 402
602 272 -30
268 -12 542
-210 -322 374
270 -558 244
-28 202 562
148 -458 494
-420 -42 188
-236 -278 -160
-110 -424 418
514...

output:

0

result:

ok answer is '0'

Test #67:

score: 0
Accepted
time: 1ms
memory: 4292kb

input:

200
61 112 145
55 -98 176
235 -88 126
5 -5 -12
-251 34 75
51 -254 196
158 304 286
151 -268 152
-38 302 10
-32 148 131
205 140 -92
-161 13 -215
-199 -181 -255
-300 -118 3
93 136 -88
173 222 17
-164 95 -128
-192 -107 -264
136 -190 -27
-164 -29 -95
-115 -59 -245
-82 -184 136
-228 297 59
-169 -103 -86
-...

output:

1

result:

ok answer is '1'

Test #68:

score: 0
Accepted
time: 1ms
memory: 4152kb

input:

200
61 112 145
55 -98 176
235 -88 126
5 -5 -12
-251 34 75
51 -254 196
158 304 286
151 -268 152
-38 302 10
-32 148 131
205 140 -92
-161 13 -215
-199 -181 -255
-300 -118 3
93 136 -88
173 222 17
-164 95 -128
-192 -107 -264
136 -190 -27
-164 -29 -95
-115 -59 -245
-82 -184 136
-228 297 59
-169 -103 -86
-...

output:

0

result:

ok answer is '0'

Test #69:

score: 0
Accepted
time: 1ms
memory: 4128kb

input:

200
61 112 145
55 -98 176
235 -88 126
5 -5 -12
-251 34 75
51 -254 196
158 304 286
151 -268 152
-38 302 10
-32 148 131
205 140 -92
-161 13 -215
-199 -181 -255
-300 -118 3
93 136 -88
173 222 17
-164 95 -128
-192 -107 -264
136 -190 -27
-164 -29 -95
-115 -59 -245
-82 -184 136
-228 297 59
-169 -103 -86
-...

output:

0

result:

ok answer is '0'

Test #70:

score: 0
Accepted
time: 0ms
memory: 4060kb

input:

4
1 0 0
2 0 0
2 2 0
2 -1 0
1 2
2 3
2 4
0 1 1
0 0 0
0 2 0
0 0 2
5 6
5 7
5 8

output:

0

result:

ok answer is '0'

Test #71:

score: 0
Accepted
time: 0ms
memory: 4160kb

input:

7
0 0 0
0 3 0
-3 3 0
0 6 0
0 9 0
0 9 3
0 9 -3
1 2
2 3
2 5
3 4
3 6
4 7
0 0 0
2 0 0
2 2 0
4 0 0
6 0 0
6 0 2
6 0 -2
8 9
9 10
9 12
10 11
10 13
11 14

output:

1

result:

ok answer is '1'

Test #72:

score: 0
Accepted
time: 0ms
memory: 4096kb

input:

7
0 0 0
0 3 0
-3 3 0
0 6 0
0 9 0
0 9 3
0 9 -3
1 2
2 3
2 5
3 4
3 6
4 7
0 0 0
2 0 0
2 2 0
4 0 0
6 0 0
6 0 2
6 0 -2
8 9
9 10
9 12
10 11
10 14
11 13

output:

0

result:

ok answer is '0'

Test #73:

score: 0
Accepted
time: 0ms
memory: 4012kb

input:

7
0 0 0
0 3 0
-3 3 0
0 6 0
0 9 0
0 9 3
0 9 -3
1 2
2 3
2 5
3 4
3 6
4 7
0 0 0
2 0 0
2 2 0
4 0 0
6 -4 0
6 0 2
6 0 -2
8 9
9 10
9 12
10 11
10 13
11 14

output:

0

result:

ok answer is '0'

Test #74:

score: 0
Accepted
time: 0ms
memory: 4008kb

input:

4
0 0 0
1 3 0
5 4 0
3 5 3
1 2
1 3
1 4
0 0 0
-1 3 0
-5 4 0
-3 5 3
5 6
5 7
5 8

output:

0

result:

ok answer is '0'

Test #75:

score: 0
Accepted
time: 0ms
memory: 4072kb

input:

3
0 0 0
0 0 1
0 0 2
1 2
1 3
10 4 6
0 0 0
5 2 3
4 5
5 6

output:

1

result:

ok answer is '1'

Test #76:

score: 0
Accepted
time: 0ms
memory: 4100kb

input:

4
0 0 0
1 3 3
-1 5 5
-10 2 2
1 2
1 3
1 4
1 1 6
0 0 0
-1 -1 10
-10 -10 4
5 6
6 7
6 8

output:

1

result:

ok answer is '1'

Test #77:

score: 0
Accepted
time: 0ms
memory: 4104kb

input:

7
0 0 0
1 0 0
-1 0 0
0 1 0
0 -1 0
0 0 1
0 0 -1
1 2
1 3
1 4
1 5
1 6
1 7
0 0 0
2 0 0
-2 0 0
0 2 0
0 -2 0
0 0 2
0 0 -2
8 9
8 10
8 11
8 12
8 13
8 14

output:

24

result:

ok answer is '24'

Test #78:

score: 0
Accepted
time: 0ms
memory: 4104kb

input:

4
0 0 0
89 89 0
-45 -44 109
-44 -45 -109
1 2
1 3
1 4
0 0 0
4 5 11
-9 -9 0
5 4 -11
5 6
5 7
5 8

output:

6

result:

ok answer is '6'

Test #79:

score: 0
Accepted
time: 0ms
memory: 4156kb

input:

5
0 0 0
9 9 0
-5 -4 11
-4 -5 -11
11 -11 1
1 2
1 3
1 4
1 5
0 0 0
4 5 11
-9 -9 0
5 4 -11
11 -11 1
6 7
6 8
6 9
6 10

output:

3

result:

ok answer is '3'

Test #80:

score: 0
Accepted
time: 0ms
memory: 4068kb

input:

4
0 0 0
9 9 0
-5 -4 11
-4 -5 -11
1 2
1 3
1 4
0 0 0
4 5 11
-9 -9 0
5 4 -11
5 6
5 7
5 8

output:

6

result:

ok answer is '6'

Test #81:

score: 0
Accepted
time: 0ms
memory: 4244kb

input:

7
0 0 0
9 9 0
4 5 11
-5 -4 11
-9 -9 0
-4 -5 -11
5 4 -11
1 2
1 3
1 4
1 5
1 6
1 7
0 0 0
89 89 0
44 45 109
-45 -44 109
-89 -89 0
-44 -45 -109
45 44 -109
8 9
8 10
8 11
8 12
8 13
8 14

output:

12

result:

ok answer is '12'

Test #82:

score: 0
Accepted
time: 0ms
memory: 4080kb

input:

7
0 0 0
9 9 0
4 5 11
-5 -4 11
-9 -9 0
-4 -5 -11
5 4 -11
1 2
1 3
1 4
1 5
1 6
1 7
0 0 0
9 9 0
4 5 11
-5 -4 11
-9 -9 0
-4 -5 -11
5 4 -11
8 9
8 10
8 11
8 12
8 13
8 14

output:

12

result:

ok answer is '12'

Test #83:

score: 0
Accepted
time: 0ms
memory: 4044kb

input:

4
0 0 0
1 0 0
0 1 0
0 0 1
1 2
1 3
1 4
0 0 0
2 0 0
0 2 0
0 0 2
5 6
5 7
5 8

output:

3

result:

ok answer is '3'