QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87716#3661. Moleculesrania__AC ✓1856ms3840kbC++142.9kb2023-03-14 04:09:502023-03-14 04:09:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-14 04:09:53]
  • 评测
  • 测评结果:AC
  • 用时:1856ms
  • 内存:3840kb
  • [2023-03-14 04:09:50]
  • 提交

answer

#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5+7, P1 = 31, P2 = 37, mod= 1e9 + 7;
#define ld long double
#define pi acos(-1)
const ld eps = 1e-9;
using pType = long double;
struct point{
    pType X, Y;
    ld angle;

    point(){
        X = Y = angle = 0;
    };

    point(pType x, pType y){
        X = x, Y = y;

        if(Y == 0)
            angle = (X < 0 ? pi : 0);
        else if(X == 0)
            angle = (Y < 0 ? 3 * pi / 2 : pi / 2);

        angle = atan2(Y, X);
        if(X > 0 and Y > 0)
            ;
        else if(X < 0 and Y > 0)
            angle = pi - angle;
        else if(X < 0 and Y < 0)
            angle = pi + angle;
        else
            angle = 2 * pi - angle;
    }

    const point operator*(const ld &factor) const{
        return point(X * factor, Y * factor);
    }
    const point operator/(const ld &factor) const {
        assert(fabs(factor) > eps);
        return point(X / factor, Y / factor);
    }

    const point operator-(const point &other) const {
        return point(X - other.X, Y - other.Y);
    }

    const point operator+(const point &other) const {
        return point(X + other.X, Y + other.Y);
    }


};
void doWork() {
    int fix[105];
    vector<int> adj[105];
    int n,m;
    cin >> n >> m;
    vector<point> p;
    for(int i = 0;i < n;++i)
    {
        ld a,b;
        cin >> a >> b;
        p.emplace_back(a,b);
        if(a != -1 && b != -1)
            fix[i] = 1;
        else
            fix[i] =0;
    }
    for(int i = 0;i < m;++i)
    {
        int u,v;
        cin >> u >> v;
        --u,--v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<point> cur(n);
    for(int i = 0;i < 1e5;++i)
    {
        for(int j = 0;j < n;++j)
        {
            if(fix[j])
                cur[j] = p[j];
            else
            {
                point ex(0.0,0.0);
                for(auto &v : adj[j])
                {
                    ex = ex + p[v];
                }
                cur[j] = (p[j] + ex / (1.0*adj[j].size()))/2;
            }
        }
        for(int j = 0;j < n;++j)
            p[j] = cur[j];
    }

    for(auto i : p)
        cout << fixed << setprecision(10) << i.X << " " << i.Y << endl;
}


int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
//    freopen("bisector.in","r",stdin);
//    freopen("bisector.out","w",stdout);
    int t = 1;
    // cout << primes.size() << endl;
    // cin >> t;
    while (t--) {
        doWork();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 9ms
memory: 3596kb

input:

3 2
0 0
-1 -1
2 0
1 2
2 3

output:

0.0000000000 0.0000000000
1.0000000000 0.0000000000
2.0000000000 0.0000000000

result:

ok good solution

Test #2:

score: 0
Accepted
time: 150ms
memory: 3724kb

input:

5 4
0 0
-1 -1
-1 -1
-1 -1
4 0
1 2
2 3
3 4
4 5

output:

0.0000000000 0.0000000000
1.0000000000 -0.0000000000
2.0000000000 -0.0000000000
3.0000000000 -0.0000000000
4.0000000000 0.0000000000

result:

ok good solution

Test #3:

score: 0
Accepted
time: 10ms
memory: 3584kb

input:

4 3
0 0
2 0
1 1
-1 -1
1 4
2 4
3 4

output:

0.0000000000 0.0000000000
2.0000000000 0.0000000000
1.0000000000 1.0000000000
1.0000000000 0.3333333333

result:

ok good solution

Test #4:

score: 0
Accepted
time: 9ms
memory: 3588kb

input:

2 1
483 55
-1 -1
1 2

output:

483.0000000000 55.0000000000
483.0000000000 55.0000000000

result:

ok good solution

Test #5:

score: 0
Accepted
time: 62ms
memory: 3588kb

input:

10 9
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
116 841
-1 -1
-1 -1
-1 -1
-1 -1
1 2
2 8
7 8
6 7
4 6
4 10
9 10
3 9
3 5

output:

116.0000000000 841.0000000000
116.0000000000 841.0000000000
116.0000000000 841.0000000000
116.0000000000 841.0000000000
116.0000000000 841.0000000000
116.0000000000 841.0000000000
116.0000000000 841.0000000000
116.0000000000 841.0000000000
116.0000000000 841.0000000000
116.0000000000 841.0000000000

result:

ok good solution

Test #6:

score: 0
Accepted
time: 61ms
memory: 3748kb

input:

10 9
809 212
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
6 9
5 6
6 7
4 6
1 6
6 10
6 8
2 6
3 6

output:

809.0000000000 212.0000000000
809.0000000000 212.0000000000
809.0000000000 212.0000000000
809.0000000000 212.0000000000
809.0000000000 212.0000000000
809.0000000000 212.0000000000
809.0000000000 212.0000000000
809.0000000000 212.0000000000
809.0000000000 212.0000000000
809.0000000000 212.0000000000

result:

ok good solution

Test #7:

score: 0
Accepted
time: 63ms
memory: 3664kb

input:

10 10
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
43 400
-1 -1
-1 -1
-1 -1
1 7
5 7
1 4
4 10
8 10
3 8
2 3
2 6
6 9
5 9

output:

43.0000000000 400.0000000000
43.0000000000 400.0000000000
43.0000000000 400.0000000000
43.0000000000 400.0000000000
43.0000000000 400.0000000000
43.0000000000 400.0000000000
43.0000000000 400.0000000000
43.0000000000 400.0000000000
43.0000000000 400.0000000000
43.0000000000 400.0000000000

result:

ok good solution

Test #8:

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

input:

10 45
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
769 439
-1 -1
-1 -1
4 9
2 9
5 9
3 9
9 10
6 9
8 9
1 9
7 9
2 4
4 5
3 4
4 10
4 6
4 8
1 4
4 7
2 5
2 3
2 10
2 6
2 8
1 2
2 7
3 5
5 10
5 6
5 8
1 5
5 7
3 10
3 6
3 8
1 3
3 7
6 10
8 10
1 10
7 10
6 8
1 6
6 7
1 8
7 8
1 7

output:

769.0000000000 439.0000000000
769.0000000000 439.0000000000
769.0000000000 439.0000000000
769.0000000000 439.0000000000
769.0000000000 439.0000000000
769.0000000000 439.0000000000
769.0000000000 439.0000000000
769.0000000000 439.0000000000
769.0000000000 439.0000000000
769.0000000000 439.0000000000

result:

ok good solution

Test #9:

score: 0
Accepted
time: 67ms
memory: 3680kb

input:

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

output:

982.0000000000 11.0000000000
982.0000000000 11.0000000000
982.0000000000 11.0000000000
982.0000000000 11.0000000000
982.0000000000 11.0000000000
982.0000000000 11.0000000000
982.0000000000 11.0000000000
982.0000000000 11.0000000000
982.0000000000 11.0000000000
982.0000000000 11.0000000000

result:

ok good solution

Test #10:

score: 0
Accepted
time: 66ms
memory: 3620kb

input:

10 22
-1 -1
830 699
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 7
6 7
4 7
7 8
1 10
1 3
1 9
1 8
3 10
8 10
6 8
5 6
2 4
4 8
4 5
3 9
2 3
3 5
8 9
2 8
2 5
5 8

output:

830.0000000000 699.0000000000
830.0000000000 699.0000000000
830.0000000000 699.0000000000
830.0000000000 699.0000000000
830.0000000000 699.0000000000
830.0000000000 699.0000000000
830.0000000000 699.0000000000
830.0000000000 699.0000000000
830.0000000000 699.0000000000
830.0000000000 699.0000000000

result:

ok good solution

Test #11:

score: 0
Accepted
time: 5ms
memory: 3600kb

input:

10 9
836 115
170 625
847 138
423 134
69 958
197 58
612 482
398 66
638 560
912 791
1 6
2 6
2 9
4 9
4 10
3 10
3 7
7 8
5 8

output:

836.0000000000 115.0000000000
170.0000000000 625.0000000000
847.0000000000 138.0000000000
423.0000000000 134.0000000000
69.0000000000 958.0000000000
197.0000000000 58.0000000000
612.0000000000 482.0000000000
398.0000000000 66.0000000000
638.0000000000 560.0000000000
912.0000000000 791.0000000000

result:

ok good solution

Test #12:

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

input:

10 9
235 57
70 633
779 707
754 104
629 812
219 906
220 90
690 104
290 712
554 766
2 4
3 4
4 9
4 7
4 8
1 4
4 5
4 6
4 10

output:

235.0000000000 57.0000000000
70.0000000000 633.0000000000
779.0000000000 707.0000000000
754.0000000000 104.0000000000
629.0000000000 812.0000000000
219.0000000000 906.0000000000
220.0000000000 90.0000000000
690.0000000000 104.0000000000
290.0000000000 712.0000000000
554.0000000000 766.0000000000

result:

ok good solution

Test #13:

score: 0
Accepted
time: 5ms
memory: 3592kb

input:

10 10
70 42
556 882
193 850
7 553
485 544
56 418
3 731
636 317
323 387
897 965
5 8
8 9
3 5
3 4
4 7
6 7
2 6
1 2
1 10
9 10

output:

70.0000000000 42.0000000000
556.0000000000 882.0000000000
193.0000000000 850.0000000000
7.0000000000 553.0000000000
485.0000000000 544.0000000000
56.0000000000 418.0000000000
3.0000000000 731.0000000000
636.0000000000 317.0000000000
323.0000000000 387.0000000000
897.0000000000 965.0000000000

result:

ok good solution

Test #14:

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

input:

10 45
907 657
86 664
164 636
634 997
96 829
132 725
813 518
682 636
189 39
467 496
8 10
5 8
7 8
8 9
1 8
4 8
3 8
2 8
6 8
5 10
7 10
9 10
1 10
4 10
3 10
2 10
6 10
5 7
5 9
1 5
4 5
3 5
2 5
5 6
7 9
1 7
4 7
3 7
2 7
6 7
1 9
4 9
3 9
2 9
6 9
1 4
1 3
1 2
1 6
3 4
2 4
4 6
2 3
3 6
2 6

output:

907.0000000000 657.0000000000
86.0000000000 664.0000000000
164.0000000000 636.0000000000
634.0000000000 997.0000000000
96.0000000000 829.0000000000
132.0000000000 725.0000000000
813.0000000000 518.0000000000
682.0000000000 636.0000000000
189.0000000000 39.0000000000
467.0000000000 496.0000000000

result:

ok good solution

Test #15:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

10 9
940 621
106 257
114 593
966 649
15 485
369 82
32 104
255 540
358 628
973 335
3 4
3 7
3 10
4 6
4 8
2 6
6 9
1 6
5 7

output:

940.0000000000 621.0000000000
106.0000000000 257.0000000000
114.0000000000 593.0000000000
966.0000000000 649.0000000000
15.0000000000 485.0000000000
369.0000000000 82.0000000000
32.0000000000 104.0000000000
255.0000000000 540.0000000000
358.0000000000 628.0000000000
973.0000000000 335.0000000000

result:

ok good solution

Test #16:

score: 0
Accepted
time: 5ms
memory: 3652kb

input:

10 22
355 567
958 426
366 303
872 699
936 45
622 755
106 336
764 142
298 139
434 82
1 4
4 9
4 10
4 5
4 7
4 6
1 9
1 10
1 5
1 6
9 10
8 9
5 9
2 9
6 9
5 10
7 10
6 10
3 8
5 8
6 8
6 7

output:

355.0000000000 567.0000000000
958.0000000000 426.0000000000
366.0000000000 303.0000000000
872.0000000000 699.0000000000
936.0000000000 45.0000000000
622.0000000000 755.0000000000
106.0000000000 336.0000000000
764.0000000000 142.0000000000
298.0000000000 139.0000000000
434.0000000000 82.0000000000

result:

ok good solution

Test #17:

score: 0
Accepted
time: 38ms
memory: 3596kb

input:

10 9
186 601
-1 -1
383 263
107 433
-1 -1
-1 -1
-1 -1
-1 -1
538 293
107 337
2 8
2 6
3 6
3 7
4 7
4 5
5 10
1 10
1 9

output:

186.0000000000 601.0000000000
383.0000000000 263.0000000000
383.0000000000 263.0000000000
107.0000000000 433.0000000000
107.0000000000 385.0000000000
383.0000000000 263.0000000000
245.0000000000 348.0000000000
383.0000000000 263.0000000000
538.0000000000 293.0000000000
107.0000000000 337.0000000000

result:

ok good solution

Test #18:

score: 0
Accepted
time: 37ms
memory: 3588kb

input:

10 9
5 522
100 701
-1 -1
-1 -1
694 214
149 692
-1 -1
580 495
-1 -1
-1 -1
8 10
4 10
1 10
9 10
3 10
2 10
5 10
6 10
7 10

output:

5.0000000000 522.0000000000
100.0000000000 701.0000000000
305.6000000000 524.8000000000
305.6000000000 524.8000000000
694.0000000000 214.0000000000
149.0000000000 692.0000000000
305.6000000000 524.8000000000
580.0000000000 495.0000000000
305.6000000000 524.8000000000
305.6000000000 524.8000000000

result:

ok good solution

Test #19:

score: 0
Accepted
time: 38ms
memory: 3580kb

input:

10 10
-1 -1
263 152
-1 -1
754 385
-1 -1
708 776
622 780
686 227
-1 -1
-1 -1
7 9
1 9
4 7
4 6
5 6
2 5
2 10
3 10
3 8
1 8

output:

664.6666666667 411.3333333333
263.0000000000 152.0000000000
545.0000000000 202.0000000000
754.0000000000 385.0000000000
485.5000000000 464.0000000000
708.0000000000 776.0000000000
622.0000000000 780.0000000000
686.0000000000 227.0000000000
643.3333333333 595.6666666667
404.0000000000 177.0000000000

result:

ok good solution

Test #20:

score: 0
Accepted
time: 37ms
memory: 3588kb

input:

10 45
963 22
-1 -1
-1 -1
835 780
603 104
-1 -1
130 110
717 554
-1 -1
-1 -1
3 5
5 9
5 6
5 7
5 8
5 10
1 5
4 5
2 5
3 9
3 6
3 7
3 8
3 10
1 3
3 4
2 3
6 9
7 9
8 9
9 10
1 9
4 9
2 9
6 7
6 8
6 10
1 6
4 6
2 6
7 8
7 10
1 7
4 7
2 7
8 10
1 8
4 8
2 8
1 10
4 10
2 10
1 4
1 2
2 4

output:

963.0000000000 22.0000000000
649.6000000000 314.0000000000
649.6000000000 314.0000000000
835.0000000000 780.0000000000
603.0000000000 104.0000000000
649.6000000000 314.0000000000
130.0000000000 110.0000000000
717.0000000000 554.0000000000
649.6000000000 314.0000000000
649.6000000000 314.0000000000

result:

ok good solution

Test #21:

score: 0
Accepted
time: 37ms
memory: 3580kb

input:

10 9
322 868
938 593
-1 -1
106 397
-1 -1
856 801
-1 -1
-1 -1
-1 -1
949 226
5 6
1 6
6 7
5 8
8 10
2 8
3 8
8 9
4 7

output:

322.0000000000 868.0000000000
938.0000000000 593.0000000000
926.0000000000 487.8000000000
106.0000000000 397.0000000000
891.0000000000 644.4000000000
856.0000000000 801.0000000000
481.0000000000 599.0000000000
926.0000000000 487.8000000000
926.0000000000 487.8000000000
949.0000000000 226.0000000000

result:

ok good solution

Test #22:

score: 0
Accepted
time: 40ms
memory: 3652kb

input:

10 22
201 738
52 928
-1 -1
-1 -1
-1 -1
598 203
-1 -1
699 547
-1 -1
310 728
3 5
3 6
3 9
3 7
1 3
3 8
2 5
5 10
5 8
2 9
2 7
2 8
2 4
6 10
1 6
9 10
7 9
8 9
4 9
7 10
4 7
4 8

output:

201.0000000000 738.0000000000
52.0000000000 928.0000000000
420.1346598797 607.8782970847
350.8810735770 732.8875520592
370.2836649699 702.7195742712
598.0000000000 203.0000000000
297.5900046275 742.2193428968
699.0000000000 547.0000000000
354.9342896807 714.3308653401
310.0000000000 728.0000000000

result:

ok good solution

Test #23:

score: 0
Accepted
time: 55ms
memory: 3680kb

input:

10 9
260 693
-1 -1
314 880
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 8
1 4
3 4
3 9
7 9
5 7
2 5
2 6
6 10

output:

260.0000000000 693.0000000000
314.0000000000 880.0000000000
314.0000000000 880.0000000000
287.0000000000 786.5000000000
314.0000000000 880.0000000000
314.0000000000 880.0000000000
314.0000000000 880.0000000000
260.0000000000 693.0000000000
314.0000000000 880.0000000000
314.0000000000 880.0000000000

result:

ok good solution

Test #24:

score: 0
Accepted
time: 54ms
memory: 3584kb

input:

10 9
-1 -1
-1 -1
-1 -1
660 977
-1 -1
-1 -1
-1 -1
855 614
-1 -1
-1 -1
8 10
9 10
4 10
1 10
3 10
2 10
7 10
6 10
5 10

output:

757.5000000000 795.5000000000
757.5000000000 795.5000000000
757.5000000000 795.5000000000
660.0000000000 977.0000000000
757.5000000000 795.5000000000
757.5000000000 795.5000000000
757.5000000000 795.5000000000
855.0000000000 614.0000000000
757.5000000000 795.5000000000
757.5000000000 795.5000000000

result:

ok good solution

Test #25:

score: 0
Accepted
time: 52ms
memory: 3752kb

input:

10 10
437 702
-1 -1
-1 -1
-1 -1
-1 -1
39 589
-1 -1
-1 -1
-1 -1
-1 -1
7 9
6 7
9 10
5 10
1 5
1 3
2 3
2 8
4 8
4 6

output:

437.0000000000 702.0000000000
277.8000000000 656.8000000000
357.4000000000 679.4000000000
118.6000000000 611.6000000000
357.4000000000 679.4000000000
39.0000000000 589.0000000000
118.6000000000 611.6000000000
198.2000000000 634.2000000000
198.2000000000 634.2000000000
277.8000000000 656.8000000000

result:

ok good solution

Test #26:

score: 0
Accepted
time: 58ms
memory: 3724kb

input:

10 45
-1 -1
-1 -1
-1 -1
-1 -1
388 394
-1 -1
940 801
-1 -1
-1 -1
-1 -1
7 10
7 9
4 7
6 7
5 7
3 7
2 7
7 8
1 7
9 10
4 10
6 10
5 10
3 10
2 10
8 10
1 10
4 9
6 9
5 9
3 9
2 9
8 9
1 9
4 6
4 5
3 4
2 4
4 8
1 4
5 6
3 6
2 6
6 8
1 6
3 5
2 5
5 8
1 5
2 3
3 8
1 3
2 8
1 2
1 8

output:

664.0000000000 597.5000000000
664.0000000000 597.5000000000
664.0000000000 597.5000000000
664.0000000000 597.5000000000
388.0000000000 394.0000000000
664.0000000000 597.5000000000
940.0000000000 801.0000000000
664.0000000000 597.5000000000
664.0000000000 597.5000000000
664.0000000000 597.5000000000

result:

ok good solution

Test #27:

score: 0
Accepted
time: 56ms
memory: 3592kb

input:

10 9
-1 -1
482 665
109 427
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
6 8
1 8
8 9
6 7
5 6
9 10
3 9
2 9
3 4

output:

295.5000000000 546.0000000000
482.0000000000 665.0000000000
109.0000000000 427.0000000000
109.0000000000 427.0000000000
295.5000000000 546.0000000000
295.5000000000 546.0000000000
295.5000000000 546.0000000000
295.5000000000 546.0000000000
295.5000000000 546.0000000000
295.5000000000 546.0000000000

result:

ok good solution

Test #28:

score: 0
Accepted
time: 58ms
memory: 3584kb

input:

10 22
-1 -1
618 374
-1 -1
-1 -1
-1 -1
-1 -1
776 984
-1 -1
-1 -1
-1 -1
4 9
1 9
2 9
3 9
6 9
4 5
4 8
4 10
2 4
4 6
1 5
1 8
1 6
5 8
2 5
3 5
8 10
2 8
3 8
3 10
7 10
2 7

output:

641.6282847587 465.2231247014
618.0000000000 374.0000000000
651.0141742316 501.4597865902
643.9433030737 474.1608536391
640.0430004778 459.1027233636
641.6031215162 465.1259754738
776.0000000000 984.0000000000
645.6292403249 480.6698518872
639.2377767160 455.9939480809
679.1466794075 610.0726230291

result:

ok good solution

Test #29:

score: 0
Accepted
time: 379ms
memory: 3612kb

input:

55 54
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
826 466
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -...

output:

826.0000000000 466.0000000000
826.0000000000 466.0000000000
826.0000000000 466.0000000000
826.0000000000 466.0000000000
826.0000000000 466.0000000000
825.9999999999 466.0000000000
826.0000000000 466.0000000000
826.0000000000 466.0000000000
825.9999999999 466.0000000000
826.0000000000 466.0000000000
...

result:

ok good solution

Test #30:

score: 0
Accepted
time: 353ms
memory: 3700kb

input:

55 54
-1 -1
-1 -1
-1 -1
469 809
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -...

output:

469.0000000000 809.0000000000
469.0000000000 809.0000000000
469.0000000000 809.0000000000
469.0000000000 809.0000000000
469.0000000000 809.0000000000
469.0000000000 809.0000000000
469.0000000000 809.0000000000
469.0000000000 809.0000000000
469.0000000000 809.0000000000
469.0000000000 809.0000000000
...

result:

ok good solution

Test #31:

score: 0
Accepted
time: 382ms
memory: 3604kb

input:

55 55
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
963 311
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -...

output:

963.0000000000 311.0000000000
963.0000000000 311.0000000000
963.0000000000 311.0000000000
963.0000000000 311.0000000000
963.0000000000 311.0000000000
963.0000000000 311.0000000000
963.0000000000 311.0000000000
963.0000000000 311.0000000000
963.0000000000 311.0000000000
963.0000000000 311.0000000000
...

result:

ok good solution

Test #32:

score: 0
Accepted
time: 703ms
memory: 3688kb

input:

55 1485
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
930 50
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 ...

output:

930.0000000000 50.0000000000
930.0000000000 50.0000000000
930.0000000000 50.0000000000
930.0000000000 50.0000000000
930.0000000000 50.0000000000
930.0000000000 50.0000000000
930.0000000000 50.0000000000
930.0000000000 50.0000000000
930.0000000000 50.0000000000
930.0000000000 50.0000000000
930.000000...

result:

ok good solution

Test #33:

score: 0
Accepted
time: 356ms
memory: 3624kb

input:

55 54
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
264 850
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -...

output:

264.0000000000 850.0000000000
264.0000000000 850.0000000000
264.0000000000 850.0000000000
264.0000000000 850.0000000000
264.0000000000 850.0000000000
264.0000000000 850.0000000000
264.0000000000 850.0000000000
264.0000000000 850.0000000000
264.0000000000 850.0000000000
264.0000000000 850.0000000000
...

result:

ok good solution

Test #34:

score: 0
Accepted
time: 533ms
memory: 3624kb

input:

55 742
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
271 211
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 ...

output:

271.0000000000 211.0000000000
271.0000000000 211.0000000000
271.0000000000 211.0000000000
271.0000000000 211.0000000000
271.0000000000 211.0000000000
271.0000000000 211.0000000000
271.0000000000 211.0000000000
271.0000000000 211.0000000000
271.0000000000 211.0000000000
271.0000000000 211.0000000000
...

result:

ok good solution

Test #35:

score: 0
Accepted
time: 17ms
memory: 3604kb

input:

55 54
659 607
300 933
928 75
710 856
206 995
81 907
328 803
716 744
285 647
853 474
943 398
435 36
89 747
579 682
176 467
319 803
766 21
434 477
416 738
519 385
857 505
238 835
999 570
931 703
638 156
257 135
179 319
196 833
749 340
730 421
759 627
214 132
644 352
558 559
971 159
858 571
951 665
821...

output:

659.0000000000 607.0000000000
300.0000000000 933.0000000000
928.0000000000 75.0000000000
710.0000000000 856.0000000000
206.0000000000 995.0000000000
81.0000000000 907.0000000000
328.0000000000 803.0000000000
716.0000000000 744.0000000000
285.0000000000 647.0000000000
853.0000000000 474.0000000000
94...

result:

ok good solution

Test #36:

score: 0
Accepted
time: 16ms
memory: 3620kb

input:

55 54
518 412
437 17
933 258
324 251
359 248
104 575
157 944
368 231
282 17
535 30
455 161
118 563
460 270
298 83
753 544
429 491
271 472
984 486
169 324
710 603
881 988
764 735
497 334
763 934
293 689
51 589
248 225
143 115
129 195
648 654
717 235
796 451
300 327
354 557
953 596
550 858
653 363
620...

output:

518.0000000000 412.0000000000
437.0000000000 17.0000000000
933.0000000000 258.0000000000
324.0000000000 251.0000000000
359.0000000000 248.0000000000
104.0000000000 575.0000000000
157.0000000000 944.0000000000
368.0000000000 231.0000000000
282.0000000000 17.0000000000
535.0000000000 30.0000000000
455...

result:

ok good solution

Test #37:

score: 0
Accepted
time: 30ms
memory: 3744kb

input:

55 55
713 493
601 526
107 723
522 626
844 715
532 294
144 15
659 476
452 724
997 443
562 405
89 465
42 766
704 281
95 373
193 310
31 559
871 931
468 760
348 333
249 203
47 234
39 224
559 113
57 674
465 246
653 670
811 433
241 512
112 852
103 972
582 803
421 353
529 1
839 83
392 577
613 954
228 359
7...

output:

713.0000000000 493.0000000000
601.0000000000 526.0000000000
107.0000000000 723.0000000000
522.0000000000 626.0000000000
844.0000000000 715.0000000000
532.0000000000 294.0000000000
144.0000000000 15.0000000000
659.0000000000 476.0000000000
452.0000000000 724.0000000000
997.0000000000 443.0000000000
5...

result:

ok good solution

Test #38:

score: 0
Accepted
time: 31ms
memory: 3620kb

input:

55 1485
78 305
609 229
497 311
99 204
863 151
97 734
243 331
54 303
537 293
12 22
577 845
859 160
932 774
362 907
629 871
573 950
603 202
7 765
891 749
578 108
794 205
430 764
331 263
965 849
884 775
744 408
218 527
126 72
131 711
965 186
72 457
334 232
754 574
14 11
307 488
286 875
897 266
239 215
...

output:

78.0000000000 305.0000000000
609.0000000000 229.0000000000
497.0000000000 311.0000000000
99.0000000000 204.0000000000
863.0000000000 151.0000000000
97.0000000000 734.0000000000
243.0000000000 331.0000000000
54.0000000000 303.0000000000
537.0000000000 293.0000000000
12.0000000000 22.0000000000
577.00...

result:

ok good solution

Test #39:

score: 0
Accepted
time: 16ms
memory: 3732kb

input:

55 54
752 347
231 283
928 341
806 611
899 454
519 440
758 527
453 391
114 168
674 279
619 55
15 760
214 289
743 884
399 231
727 253
637 401
163 392
157 142
521 262
786 496
597 640
2 445
748 383
890 951
165 950
665 954
602 623
616 302
202 113
190 23
606 656
854 368
280 752
348 550
457 596
749 993
641...

output:

752.0000000000 347.0000000000
231.0000000000 283.0000000000
928.0000000000 341.0000000000
806.0000000000 611.0000000000
899.0000000000 454.0000000000
519.0000000000 440.0000000000
758.0000000000 527.0000000000
453.0000000000 391.0000000000
114.0000000000 168.0000000000
674.0000000000 279.0000000000
...

result:

ok good solution

Test #40:

score: 0
Accepted
time: 10ms
memory: 3636kb

input:

55 742
540 864
330 479
845 491
19 598
332 114
569 366
351 60
184 642
296 429
147 841
529 585
537 512
289 880
734 108
441 63
121 332
612 612
872 500
393 593
697 681
518 837
227 354
302 16
209 937
723 865
386 356
867 110
623 371
119 552
169 924
281 838
900 745
923 844
735 83
102 800
259 639
61 864
210...

output:

540.0000000000 864.0000000000
330.0000000000 479.0000000000
845.0000000000 491.0000000000
19.0000000000 598.0000000000
332.0000000000 114.0000000000
569.0000000000 366.0000000000
351.0000000000 60.0000000000
184.0000000000 642.0000000000
296.0000000000 429.0000000000
147.0000000000 841.0000000000
52...

result:

ok good solution

Test #41:

score: 0
Accepted
time: 215ms
memory: 3604kb

input:

55 54
-1 -1
745 403
592 36
840 326
296 223
-1 -1
-1 -1
-1 -1
355 48
143 156
-1 -1
-1 -1
994 924
30 798
961 461
785 2
418 688
-1 -1
809 670
-1 -1
-1 -1
-1 -1
-1 -1
771 696
-1 -1
995 356
28 578
208 241
-1 -1
567 637
-1 -1
375 232
-1 -1
-1 -1
-1 -1
-1 -1
956 413
87 972
944 219
258 626
83 112
-1 -1
9 21...

output:

619.5000000000 751.0000000000
745.0000000000 403.0000000000
592.0000000000 36.0000000000
840.0000000000 326.0000000000
296.0000000000 223.0000000000
28.8571428571 672.2857142857
85.5000000000 367.0000000000
28.5714285714 640.8571428571
355.0000000000 48.0000000000
143.0000000000 156.0000000000
988.5...

result:

ok good solution

Test #42:

score: 0
Accepted
time: 236ms
memory: 3728kb

input:

55 54
-1 -1
307 812
-1 -1
-1 -1
426 231
848 819
-1 -1
666 136
-1 -1
863 615
-1 -1
289 798
-1 -1
-1 -1
717 519
93 158
803 494
-1 -1
828 517
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
362 704
512 50
-1 -1
560 727
-1 -1
902 680
631 838
428 561
-1 -1
711 935
958 42
-1 -1
970 979
-1 -1
-1 -1
-1 -1
-...

output:

548.8928571429 584.5714285714
307.0000000000 812.0000000000
548.8928571429 584.5714285714
548.8928571429 584.5714285714
426.0000000000 231.0000000000
848.0000000000 819.0000000000
548.8928571429 584.5714285714
666.0000000000 136.0000000000
548.8928571429 584.5714285714
863.0000000000 615.0000000000
...

result:

ok good solution

Test #43:

score: 0
Accepted
time: 188ms
memory: 3604kb

input:

55 55
-1 -1
-1 -1
484 322
-1 -1
331 104
715 886
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
978 111
418 176
-1 -1
414 183
556 541
-1 -1
695 810
855 93
192 170
487 771
-1 -1
639 631
-1 -1
199 698
628 873
-1 -1
-1 -1
265 426
521 226
776 109
-1 -1
-1 -1
446 107
400 203
-1 -1
75 777
654 395
-1 -1
875 36
-1 -1
-1 -1
1...

output:

372.5000000000 522.0000000000
327.3333333333 372.3333333333
484.0000000000 322.0000000000
537.0000000000 367.0000000000
331.0000000000 104.0000000000
715.0000000000 886.0000000000
671.0000000000 432.0000000000
309.2500000000 278.5000000000
641.0000000000 634.0000000000
691.8000000000 295.8000000000
...

result:

ok good solution

Test #44:

score: 0
Accepted
time: 390ms
memory: 3784kb

input:

55 1485
-1 -1
-1 -1
302 292
175 660
-1 -1
952 58
-1 -1
-1 -1
-1 -1
-1 -1
419 750
666 230
793 285
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
361 935
936 382
-1 -1
639 684
529 769
-1 -1
424 880
959 514
104 87
-1 -1
-1 -1
-1 -1
416 776
320 229
902 179
669 81
986 183
-1 -1
-1 -1
846 679
-1 -1
-1 -1
-1 -1
828 642
-1 ...

output:

549.7500000000 507.0357142857
549.7500000000 507.0357142857
302.0000000000 292.0000000000
175.0000000000 660.0000000000
549.7500000000 507.0357142857
952.0000000000 58.0000000000
549.7500000000 507.0357142857
549.7500000000 507.0357142857
549.7500000000 507.0357142857
549.7500000000 507.0357142857
4...

result:

ok good solution

Test #45:

score: 0
Accepted
time: 187ms
memory: 3704kb

input:

55 54
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
202 734
-1 -1
856 815
798 215
306 464
953 967
874 982
433 434
254 582
-1 -1
-1 -1
-1 -1
895 288
-1 -1
-1 -1
330 37
759 90
-1 -1
677 530
-1 -1
-1 -1
236 223
-1 -1
624 974
600 36
-1 -1
-1 -1
-1 -1
820 586
-1 -1
657 293
-1 -1
570 277
703 297
252 654
-1 -1
421 860
443...

output:

443.0000000000 857.0000000000
333.8300000000 385.7500000000
364.4300000000 733.1500000000
202.0000000000 734.0000000000
520.6600000000 431.1000000000
202.0000000000 734.0000000000
333.8300000000 385.7500000000
856.0000000000 815.0000000000
798.0000000000 215.0000000000
306.0000000000 464.0000000000
...

result:

ok good solution

Test #46:

score: 0
Accepted
time: 309ms
memory: 3704kb

input:

55 742
37 608
-1 -1
-1 -1
578 457
-1 -1
626 603
-1 -1
240 500
889 466
552 681
-1 -1
471 342
-1 -1
719 469
-1 -1
643 221
619 999
452 345
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
118 666
-1 -1
-1 -1
-1 -1
503 312
-1 -1
75 390
-1 -1
698 474
-1 -1
323 243
-1 -1
-1 -1
-1 -1
-1 -1
769 532
484 742
322 567
-1 -1
-1 -1...

output:

37.0000000000 608.0000000000
479.5464495930 541.9180605278
529.1675251120 562.0923302599
578.0000000000 457.0000000000
447.4440381317 551.3797345815
626.0000000000 603.0000000000
483.7289274639 542.3379978360
240.0000000000 500.0000000000
889.0000000000 466.0000000000
552.0000000000 681.0000000000
4...

result:

ok good solution

Test #47:

score: 0
Accepted
time: 284ms
memory: 3600kb

input:

55 54
-1 -1
-1 -1
-1 -1
897 973
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
998 75
-1 -1
382 719
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
520 852
-1 -1
-1 -1
2 491
-1 -1
-1 -1
-1 -1
182 855
-1 -1
88 809
632 58
451 785
-1 -1
-1 -1
873 382
-1 -1
-1 -1
835 736
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
552 604
-1 -1
-1 -1
-1 -1...

output:

628.4000000000 461.4000000000
874.8000000000 203.8000000000
70.8000000000 745.4000000000
897.0000000000 973.0000000000
873.0000000000 382.0000000000
788.6000000000 462.6000000000
382.0000000000 719.0000000000
36.4000000000 618.2000000000
501.5000000000 694.5000000000
998.0000000000 75.0000000000
397...

result:

ok good solution

Test #48:

score: 0
Accepted
time: 276ms
memory: 3700kb

input:

55 54
83 45
-1 -1
-1 -1
185 2
42 383
-1 -1
714 753
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
820 239
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
874 991
-1 -1
389 497
-1 -1
-1 -1
-1 -1
-1 -1
411 397
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
578 178
-1 -1
-1 -1
-1 -1
-1 -1
449 558
246 420
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
2...

output:

83.0000000000 45.0000000000
438.3571428571 457.8571428571
438.3571428571 457.8571428571
185.0000000000 2.0000000000
42.0000000000 383.0000000000
438.3571428571 457.8571428571
714.0000000000 753.0000000000
438.3571428571 457.8571428571
438.3571428571 457.8571428571
438.3571428571 457.8571428571
438.3...

result:

ok good solution

Test #49:

score: 0
Accepted
time: 297ms
memory: 3572kb

input:

55 55
-1 -1
-1 -1
-1 -1
-1 -1
42 471
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
930 17
261 19
-1 -1
-1 -1
-1 -1
-1 -1
441 951
482 34
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
598 363
-1 -1
-1 -1
-1 -1
759 670
-1 -1
-1 -1
-1 -1
591 152
-1 -1
915 65
-1 -1
76 261
-1 -1
-1 -1
-1 -1
-1 -1
457 828
962 905
...

output:

698.6250000000 554.8750000000
738.8750000000 631.6250000000
505.2000000000 99.8000000000
249.0000000000 309.3333333333
42.0000000000 471.0000000000
59.0000000000 366.0000000000
459.3333333333 769.0000000000
481.4285714286 35.8571428571
427.0000000000 236.0000000000
928.4285714286 305.0000000000
930....

result:

ok good solution

Test #50:

score: 0
Accepted
time: 558ms
memory: 3784kb

input:

55 1485
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
69 201
-1 -1
-1 -1
662 940
-1 -1
-1 -1
-1 -1
683 271
-1 -1
64 322
-1 -1
732 288
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
258 229
889 259
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
233 424
315 195
-1 -1
-1 -1
-1 -1
711 666
953 ...

output:

536.3571428571 427.7142857143
536.3571428571 427.7142857143
536.3571428571 427.7142857143
536.3571428571 427.7142857143
536.3571428571 427.7142857143
536.3571428571 427.7142857143
536.3571428571 427.7142857143
536.3571428571 427.7142857143
69.0000000000 201.0000000000
536.3571428571 427.7142857143
5...

result:

ok good solution

Test #51:

score: 0
Accepted
time: 281ms
memory: 3612kb

input:

55 54
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
592 614
962 908
-1 -1
-1 -1
-1 -1
-1 -1
679 394
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
892 779
179 177
-1 -1
-1 -1
-1 -1
201 536
-1 -1
903 195
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
572 441
-1 -1
-1 -1
-1 -1
354 101
-1 -1
-1 -1
-1 -1
...

output:

777.3125000000 700.0000000000
420.8125000000 399.0000000000
474.0000000000 704.0000000000
662.0000000000 437.0000000000
572.0000000000 441.0000000000
549.0000000000 777.5000000000
688.5000000000 449.5000000000
354.0000000000 101.0000000000
592.0000000000 614.0000000000
962.0000000000 908.0000000000
...

result:

ok good solution

Test #52:

score: 0
Accepted
time: 403ms
memory: 3648kb

input:

55 742
593 66
-1 -1
-1 -1
961 473
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
2 531
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
45 370
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
336 315
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
484 20
-1 -1
-1 -1
14 505
-1 -1
277 419
-1 -1
-1 -1
317 598
276 28
-1 -...

output:

593.0000000000 66.0000000000
371.2296404452 310.8264086037
353.8687802263 320.0173258392
961.0000000000 473.0000000000
403.0384101862 313.8431438375
381.7784283317 332.8546232895
412.2631876437 322.7789799107
373.9101518165 326.7107040201
355.0571160273 348.0141316769
2.0000000000 531.0000000000
369...

result:

ok good solution

Test #53:

score: 0
Accepted
time: 664ms
memory: 3672kb

input:

100 99
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
102 151
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 ...

output:

101.9982858293 150.9974703500
101.9719078531 150.9585436279
102.0000000000 151.0000000000
101.9861996038 150.9796343668
101.9931946799 150.9899571975
101.9977153287 150.9966284462
101.9836951528 150.9759384779
101.9692217594 150.9545796838
101.9759422083 150.9644972395
101.9687011238 150.9538113672
...

result:

ok good solution

Test #54:

score: 0
Accepted
time: 719ms
memory: 3668kb

input:

100 99
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1...

output:

155.0000000000 845.0000000000
155.0000000000 845.0000000000
155.0000000000 845.0000000000
155.0000000000 845.0000000000
155.0000000000 845.0000000000
155.0000000000 845.0000000000
155.0000000000 845.0000000000
155.0000000000 845.0000000000
155.0000000000 845.0000000000
155.0000000000 845.0000000000
...

result:

ok good solution

Test #55:

score: 0
Accepted
time: 679ms
memory: 3688kb

input:

100 100
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -...

output:

743.9999999840 815.9999999825
743.9999999966 815.9999999963
743.9999999971 815.9999999969
743.9999999819 815.9999999802
743.9999999818 815.9999999800
743.9999999825 815.9999999808
743.9999999853 815.9999999838
743.9999999846 815.9999999831
743.9999999818 815.9999999800
743.9999999840 815.9999999825
...

result:

ok good solution

Test #56:

score: 0
Accepted
time: 1856ms
memory: 3808kb

input:

100 4950
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
397 558
-1 -1
-1 -1
-...

output:

397.0000000000 558.0000000000
397.0000000000 558.0000000000
397.0000000000 558.0000000000
397.0000000000 558.0000000000
397.0000000000 558.0000000000
397.0000000000 558.0000000000
397.0000000000 558.0000000000
397.0000000000 558.0000000000
397.0000000000 558.0000000000
397.0000000000 558.0000000000
...

result:

ok good solution

Test #57:

score: 0
Accepted
time: 653ms
memory: 3620kb

input:

100 99
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1...

output:

802.0000000000 491.0000000000
802.0000000000 491.0000000000
802.0000000000 491.0000000000
802.0000000000 491.0000000000
802.0000000000 491.0000000000
802.0000000000 491.0000000000
802.0000000000 491.0000000000
802.0000000000 491.0000000000
802.0000000000 491.0000000000
802.0000000000 491.0000000000
...

result:

ok good solution

Test #58:

score: 0
Accepted
time: 1232ms
memory: 3724kb

input:

100 2475
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
317 975
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-...

output:

317.0000000000 975.0000000000
317.0000000000 975.0000000000
317.0000000000 975.0000000000
317.0000000000 975.0000000000
317.0000000000 975.0000000000
317.0000000000 975.0000000000
317.0000000000 975.0000000000
317.0000000000 975.0000000000
317.0000000000 975.0000000000
317.0000000000 975.0000000000
...

result:

ok good solution

Test #59:

score: 0
Accepted
time: 27ms
memory: 3620kb

input:

100 99
128 617
589 596
470 647
136 551
998 646
302 309
518 178
74 171
952 22
433 31
396 171
468 74
869 716
394 734
964 522
634 182
961 118
567 636
835 859
903 330
614 521
605 64
955 620
501 963
431 84
790 387
550 175
32 724
352 933
164 338
962 84
271 867
464 239
764 904
254 282
306 968
797 558
267 5...

output:

128.0000000000 617.0000000000
589.0000000000 596.0000000000
470.0000000000 647.0000000000
136.0000000000 551.0000000000
998.0000000000 646.0000000000
302.0000000000 309.0000000000
518.0000000000 178.0000000000
74.0000000000 171.0000000000
952.0000000000 22.0000000000
433.0000000000 31.0000000000
396...

result:

ok good solution

Test #60:

score: 0
Accepted
time: 27ms
memory: 3716kb

input:

100 99
384 349
595 705
183 793
921 154
409 377
37 130
19 983
504 222
5 998
570 943
329 760
14 296
476 326
166 133
209 485
185 229
568 212
173 514
175 198
698 736
152 38
389 897
195 925
126 481
718 261
484 52
801 598
262 392
623 413
649 363
490 590
707 830
640 114
626 336
875 814
819 292
359 693
371 ...

output:

384.0000000000 349.0000000000
595.0000000000 705.0000000000
183.0000000000 793.0000000000
921.0000000000 154.0000000000
409.0000000000 377.0000000000
37.0000000000 130.0000000000
19.0000000000 983.0000000000
504.0000000000 222.0000000000
5.0000000000 998.0000000000
570.0000000000 943.0000000000
329....

result:

ok good solution

Test #61:

score: 0
Accepted
time: 27ms
memory: 3768kb

input:

100 100
997 944
372 38
450 981
658 193
888 232
324 108
571 172
26 288
276 733
107 529
66 368
792 192
978 936
365 514
30 574
548 651
157 640
370 414
773 361
351 361
1000 389
500 154
982 575
134 728
827 421
329 209
605 308
496 476
160 321
181 175
278 849
584 253
920 145
922 364
959 904
25 715
200 4
87...

output:

997.0000000000 944.0000000000
372.0000000000 38.0000000000
450.0000000000 981.0000000000
658.0000000000 193.0000000000
888.0000000000 232.0000000000
324.0000000000 108.0000000000
571.0000000000 172.0000000000
26.0000000000 288.0000000000
276.0000000000 733.0000000000
107.0000000000 529.0000000000
66...

result:

ok good solution

Test #62:

score: 0
Accepted
time: 32ms
memory: 3840kb

input:

100 4950
49 58
868 125
519 335
157 37
362 924
358 934
692 338
655 715
23 968
906 21
487 17
692 263
319 833
670 623
503 420
311 914
940 75
958 89
564 811
990 987
753 16
721 589
186 993
811 708
921 211
30 961
730 57
142 179
352 440
804 545
961 509
320 240
195 918
627 17
306 641
816 162
29 428
481 324
...

output:

49.0000000000 58.0000000000
868.0000000000 125.0000000000
519.0000000000 335.0000000000
157.0000000000 37.0000000000
362.0000000000 924.0000000000
358.0000000000 934.0000000000
692.0000000000 338.0000000000
655.0000000000 715.0000000000
23.0000000000 968.0000000000
906.0000000000 21.0000000000
487.0...

result:

ok good solution

Test #63:

score: 0
Accepted
time: 29ms
memory: 3740kb

input:

100 99
462 946
14 419
459 991
395 173
465 699
820 50
377 32
851 161
373 281
875 186
558 274
349 835
328 516
699 482
539 5
370 354
848 559
28 313
389 931
283 434
182 683
233 851
331 781
261 991
547 862
670 734
989 264
594 148
522 446
119 398
192 300
339 284
305 200
145 145
461 112
573 545
682 860
19 ...

output:

462.0000000000 946.0000000000
14.0000000000 419.0000000000
459.0000000000 991.0000000000
395.0000000000 173.0000000000
465.0000000000 699.0000000000
820.0000000000 50.0000000000
377.0000000000 32.0000000000
851.0000000000 161.0000000000
373.0000000000 281.0000000000
875.0000000000 186.0000000000
558...

result:

ok good solution

Test #64:

score: 0
Accepted
time: 23ms
memory: 3652kb

input:

100 2475
849 936
431 950
793 93
139 308
946 932
654 589
70 201
551 724
933 902
515 67
218 203
416 467
88 909
685 636
845 868
857 298
886 449
342 715
844 38
617 290
100 196
260 472
746 965
206 206
250 178
743 628
487 222
167 999
630 328
499 285
81 801
492 944
665 412
99 477
594 71
836 900
696 439
415...

output:

849.0000000000 936.0000000000
431.0000000000 950.0000000000
793.0000000000 93.0000000000
139.0000000000 308.0000000000
946.0000000000 932.0000000000
654.0000000000 589.0000000000
70.0000000000 201.0000000000
551.0000000000 724.0000000000
933.0000000000 902.0000000000
515.0000000000 67.0000000000
218...

result:

ok good solution

Test #65:

score: 0
Accepted
time: 352ms
memory: 3740kb

input:

100 99
-1 -1
796 176
-1 -1
948 776
-1 -1
233 485
445 637
-1 -1
741 704
-1 -1
-1 -1
829 199
53 478
220 406
-1 -1
784 751
-1 -1
242 203
208 292
899 144
-1 -1
336 682
660 710
-1 -1
-1 -1
785 292
155 60
-1 -1
494 35
4 816
839 266
976 980
-1 -1
-1 -1
-1 -1
216 383
-1 -1
714 95
151 886
818 993
-1 -1
-1 -1...

output:

270.0000000000 782.0000000000
796.0000000000 176.0000000000
441.3333333333 758.0000000000
948.0000000000 776.0000000000
654.0000000000 318.0000000000
233.0000000000 485.0000000000
445.0000000000 637.0000000000
451.3333333333 319.3333333333
741.0000000000 704.0000000000
469.5000000000 336.0000000000
...

result:

ok good solution

Test #66:

score: 0
Accepted
time: 347ms
memory: 3620kb

input:

100 99
-1 -1
-1 -1
221 348
-1 -1
-1 -1
359 141
982 64
-1 -1
113 297
-1 -1
147 419
-1 -1
-1 -1
118 26
211 332
274 897
-1 -1
694 392
-1 -1
-1 -1
-1 -1
-1 -1
378 854
174 420
-1 -1
99 576
435 529
-1 -1
-1 -1
-1 -1
941 533
-1 -1
776 857
-1 -1
355 682
865 562
326 660
878 519
474 824
-1 -1
163 19
-1 -1
-1 ...

output:

394.9800000000 501.8200000000
394.9800000000 501.8200000000
221.0000000000 348.0000000000
394.9800000000 501.8200000000
394.9800000000 501.8200000000
359.0000000000 141.0000000000
982.0000000000 64.0000000000
394.9800000000 501.8200000000
113.0000000000 297.0000000000
394.9800000000 501.8200000000
1...

result:

ok good solution

Test #67:

score: 0
Accepted
time: 352ms
memory: 3672kb

input:

100 100
-1 -1
463 246
522 213
822 216
278 652
-1 -1
-1 -1
864 213
605 950
-1 -1
276 432
-1 -1
174 894
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
594 20
76 683
996 233
-1 -1
-1 -1
583 551
581 68
467 362
-1 -1
949 883
-1 -1
92 39
-1 -1
-1 -1
701 524
164 873
-1 -1
-1 -1
0 663
-1 -1
634 753
343 128
-1 -1
-1 -1...

output:

306.0000000000 570.5000000000
463.0000000000 246.0000000000
522.0000000000 213.0000000000
822.0000000000 216.0000000000
278.0000000000 652.0000000000
536.0000000000 458.0000000000
403.0000000000 187.0000000000
864.0000000000 213.0000000000
605.0000000000 950.0000000000
392.7500000000 356.7500000000
...

result:

ok good solution

Test #68:

score: 0
Accepted
time: 964ms
memory: 3768kb

input:

100 4950
-1 -1
573 528
633 79
-1 -1
-1 -1
-1 -1
58 756
416 725
848 651
981 929
-1 -1
-1 -1
479 879
830 342
367 669
-1 -1
-1 -1
-1 -1
33 679
340 959
757 70
-1 -1
899 790
38 402
171 134
959 105
99 958
-1 -1
377 963
-1 -1
-1 -1
-1 -1
-1 -1
277 887
846 95
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
398 443
-1 -1
-1 -...

output:

519.2600000000 579.4000000000
573.0000000000 528.0000000000
633.0000000000 79.0000000000
519.2600000000 579.4000000000
519.2600000000 579.4000000000
519.2600000000 579.4000000000
58.0000000000 756.0000000000
416.0000000000 725.0000000000
848.0000000000 651.0000000000
981.0000000000 929.0000000000
51...

result:

ok good solution

Test #69:

score: 0
Accepted
time: 346ms
memory: 3644kb

input:

100 99
845 808
-1 -1
887 579
664 501
947 14
-1 -1
315 353
-1 -1
173 993
963 216
60 143
-1 -1
778 765
119 184
-1 -1
411 114
155 677
714 255
294 712
-1 -1
288 788
951 266
606 251
843 979
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
285 223
724 577
-1 -1
-1 -1
605 181
-1 -1
-1 -1
158 718
-1 -1
-1 -1...

output:

845.0000000000 808.0000000000
559.0000000000 446.5000000000
887.0000000000 579.0000000000
664.0000000000 501.0000000000
947.0000000000 14.0000000000
155.0000000000 677.0000000000
315.0000000000 353.0000000000
470.7142857143 556.0634920635
173.0000000000 993.0000000000
963.0000000000 216.0000000000
6...

result:

ok good solution

Test #70:

score: 0
Accepted
time: 636ms
memory: 3660kb

input:

100 2475
-1 -1
287 56
716 882
895 284
-1 -1
306 534
-1 -1
720 596
-1 -1
-1 -1
-1 -1
547 169
-1 -1
-1 -1
-1 -1
301 45
165 698
830 671
735 827
127 98
416 228
-1 -1
-1 -1
-1 -1
-1 -1
478 614
396 923
-1 -1
-1 -1
374 974
-1 -1
-1 -1
-1 -1
44 262
-1 -1
-1 -1
862 398
-1 -1
578 179
-1 -1
577 159
-1 -1
-1 -1...

output:

518.7995377918 483.3533521597
287.0000000000 56.0000000000
716.0000000000 882.0000000000
895.0000000000 284.0000000000
508.0122555419 508.8721599750
306.0000000000 534.0000000000
475.4068945062 506.6578942448
720.0000000000 596.0000000000
497.1901655006 507.8675801742
513.1760175706 493.7531731871
5...

result:

ok good solution

Test #71:

score: 0
Accepted
time: 507ms
memory: 3608kb

input:

100 99
-1 -1
361 166
-1 -1
355 961
366 485
602 336
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
640 330
489 166
402 139
-1 -1
679 539
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
757 566
-1 -1
-1 -1
-1 -1
616 266
-1 -1
867 642
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
70 749
-1 -1
755 96
-1 -1
-1 -1
289 756
-1 -1
-1 -1
-1 ...

output:

645.2500000000 536.5000000000
361.0000000000 166.0000000000
797.0000000000 308.0000000000
355.0000000000 961.0000000000
366.0000000000 485.0000000000
602.0000000000 336.0000000000
754.4615384615 391.5384615385
731.5000000000 328.0000000000
429.6000000000 654.2000000000
755.6666666667 252.6666666667
...

result:

ok good solution

Test #72:

score: 0
Accepted
time: 502ms
memory: 3684kb

input:

100 99
-1 -1
867 722
-1 -1
-1 -1
-1 -1
-1 -1
264 815
-1 -1
11 395
-1 -1
-1 -1
-1 -1
-1 -1
804 924
-1 -1
418 964
-1 -1
-1 -1
-1 -1
-1 -1
93 768
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
282 88
-1 -1
-1 -1
824 519
-1 -1
46 746
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
29 947
156 264
835 804
780 569
24...

output:

434.2400000000 569.3200000000
867.0000000000 722.0000000000
434.2400000000 569.3200000000
434.2400000000 569.3200000000
434.2400000000 569.3200000000
434.2400000000 569.3200000000
264.0000000000 815.0000000000
434.2400000000 569.3200000000
11.0000000000 395.0000000000
434.2400000000 569.3200000000
4...

result:

ok good solution

Test #73:

score: 0
Accepted
time: 507ms
memory: 3624kb

input:

100 100
-1 -1
881 876
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
645 484
-1 -1
-1 -1
616 690
-1 -1
-1 -1
269 738
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
349 761
-1 -1
-1 -1
764 807
-1 -1
70 934
-1 -1
319 765
-1 -1
860 507
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
761 72
-1 -1
-1 -1
-1 -...

output:

665.0000000000 407.7142857143
881.0000000000 876.0000000000
861.6666666667 806.6666666667
298.6000000000 293.0000000000
738.3333333333 434.8333333333
471.0000000000 634.5000000000
705.0000000000 255.1428571429
659.0000000000 420.3333333333
650.0000000000 464.9285714286
803.1666666667 714.6666666667
...

result:

ok good solution

Test #74:

score: 0
Accepted
time: 1399ms
memory: 3828kb

input:

100 4950
388 522
792 4
-1 -1
-1 -1
-1 -1
467 482
605 265
-1 -1
181 736
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
85 666
-1 -1
-1 -1
-1 -1
977 455
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
55 109
21 671
-1 -1
150 627
-1 -1
514 266
98 882
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
65 116
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1...

output:

388.0000000000 522.0000000000
792.0000000000 4.0000000000
315.4400000000 429.0000000000
315.4400000000 429.0000000000
315.4400000000 429.0000000000
467.0000000000 482.0000000000
605.0000000000 265.0000000000
315.4400000000 429.0000000000
181.0000000000 736.0000000000
315.4400000000 429.0000000000
31...

result:

ok good solution

Test #75:

score: 0
Accepted
time: 518ms
memory: 3744kb

input:

100 99
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
705 719
709 38
-1 -1
-1 -1
416 446
-1 -1
-1 -1
321 738
-1 -1
754 161
-1 -1
-1 -1
257 453
576 844
789 33
-1 -1
-1 -1
-1 -1
201 608
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
891 8
-1 -1
628 819
-1 -1
-1 -1
-1 -1
-1 -1
776 541
-1 -1
-1 -1
331 870
-1 -1
-...

output:

679.4615384615 282.6923076923
786.3333333333 320.6666666667
635.8842592593 725.5444444444
616.4953703704 424.8777777778
522.9166666667 562.8000000000
786.3333333333 320.6666666667
474.5000000000 778.5000000000
921.5000000000 86.0000000000
705.0000000000 719.0000000000
709.0000000000 38.0000000000
74...

result:

ok good solution

Test #76:

score: 0
Accepted
time: 958ms
memory: 3780kb

input:

100 2475
-1 -1
427 754
-1 -1
-1 -1
69 721
-1 -1
467 311
-1 -1
870 234
695 344
-1 -1
-1 -1
-1 -1
-1 -1
205 595
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
632 223
332 892
-1 -1
-1 -1
-1 -1
17 606
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
493 435
229 307
-1 -1
-1 -1
375 903
-1 -1
-1 -1
146 778
631 939
603 875
-1 -1...

output:

492.3426211279 575.1582719848
427.0000000000 754.0000000000
451.6881285688 576.2108584995
484.5045263947 572.9515271994
69.0000000000 721.0000000000
504.1477197755 558.4430676082
467.0000000000 311.0000000000
495.2079937492 553.2075360327
870.0000000000 234.0000000000
695.0000000000 344.0000000000
4...

result:

ok good solution