Parelles de punts consecutius que estan a prop X67106

Statement

En aquest exercici us donem un programa que heu de completar. Al principi del programa es defineix un struct Point, que defineix un punt sobre el pla 2D amb coordenades enteres. El programa principal llegeix varis casos d’entrada. Cada cas consisteix en la descripció d’una llista de punts. Per a cada cas, el programa principal crida a una funció anomenada compute que és l’única que heu d’implementar (no heu de canviar res més). La funció compute rep la llista de punts com a paràmetre, i també rep un paràmetre enter distance, i retorna el nombre de parelles de punts que apareixen consecutivament a la llista, i tals que la distància (eucliciana) entre ells és menor o igual a distance.

Aquest és el codi que heu de completar:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Point {
    int x, y;
};

typedef vector<Point> VPoint;

// Afegiu funcions auxiliars si voleu.
// ...


// Pre:  v conté com a mínim un punt.
//       d >= 1
// Post: Retorna el nombre de parelles de punts que apareixen consecutivament a v,
//       i tals que la distància entre ells és menor o igual a d.
int compute(VPoint &v, int distance)
{
    // Implementeu aquesta funció.
    // ...
}

int main()
{
    int n, d;
    while (cin >> n >> d) {
        VPoint v(n);
        for (int i = 0; i < n; i++)
            cin >> v[i].x >> v[i].y;
        cout << compute(v, d) << endl;
    }
}

Entrada

L’entrada té varis casos. Cada cas comença amb dos naturals positius $n,distance$ majors o iguals a 1 en una primera línia. En una segona línia hi ha la descripció d’una llista d’ $n$ punts, amb les seves dues coordenades x,y (enteres). De fet, no us heu de preocupar massa per com son aquestes entrades perquè el programa que us donem ja té la part de lectura implementada. Només us heu de preocupar d’implementar la funció compute abans esmentada.

Sortida

Per a cada cas, el programa ha d’escriure en una nova línia el corresponent nombre de parelles de punts consecutius a la llista tals que la distància entre ells és menor o igual a distance.De fet, no us heu de preocupar massa per com son aquestes sortides perquè el programa que us donem ja té la part d’escriptura implementada. Només us heu de preocupar d’implementar la funció compute abans esmentada.

Observació

Avaluació sobre 10 punts:

Solució lenta: 5 punts.
solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta, de cost lineal i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.

Public test cases

Input

5 4
10 6  2 1  4 0  6 3  1 8
5 1
5 3  7 4  9 10  2 0  10 8
5 20
0 4  6 0  10 3  10 10  7 10
10 5
7 -1  -9 -3  6 6  5 8  2 4  10 0  10 -8  -8 5  7 9  -3 -2
10 10
-1 1  1 -9  0 -1  -4 1  2 7  -5 9  8 0  4 2  -7 -1  -7 7
8 66
-56 -35  11 -5  78 41  -100 -44  -95 -37  8 -38  7 -81  -73 -70
17 66
-28 -18  21 30  -82 5  16 -34  -3 40  30 -32  35 94  13 50  -46 -93  -23 96  58 -17  51 -79  91 63  28 60  41 8  -99 -88  91 -28
16 66
59 27  59 75  -77 -52  -46 -8  33 -53  55 -17  -48 62  10 -53  -31 94  98 -10  84 61  69 44  -49 -74  -5 -87  67 17  6 25
20 66
-36 -50  -83 12  4 9  96 52  -87 -22  54 25  88 -100  95 31  48 -16  15 -42  -98 -92  9 -71  -47 23  96 70  -72 -29  -87 -58  21 82  4 -76  -10 -1  26 4
5 66
-21 -72  -35 -71  73 96  78 -93  -40 86
10 66
-82 -5  89 -29  68 35  -59 46  -95 -96  88 -24  86 -59  -50 -74  -9 77  -20 68
5 66
-42 83  86 -69  79 13  -62 89  -2 98
7 66
43 87  -72 10  21 -31  -45 -24  -76 93  52 -91  85 -99
7 66
-25 28  -35 93  -16 -26  76 -31  5 4  32 -7  -8 -71
20 66
-51 73  -74 -22  -68 47  -3 -12  73 21  -70 24  31 -86  -24 -34  -61 54  32 -68  -63 -95  58 -44  -40 -39  88 53  53 68  93 53  -10 -81  -70 22  16 27  60 -61
10 66
91 13  29 55  89 95  45 -7  -24 27  -20 -69  -16 37  -9 45  -26 94  -53 92
8 66
100 -19  6 80  54 72  7 13  -90 5  -47 24  -67 -92  -38 78
6 66
55 -96  -21 -65  -65 13  22 -23  -43 46  -80 -46
20 66
57 -46  69 -38  84 22  85 -10  -65 95  45 -12  18 28  -54 81  6 49  -15 10  78 -30  -5 -10  92 72  -3 -12  43 52  -75 -1  56 44  12 39  -34 -4  80 -49
9 66
24 -11  59 -48  36 -11  8 -16  24 68  -38 95  -38 2  86 85  100 -27
4 66
51 -52  76 -44  93 -13  95 -92
17 66
24 -41  74 -52  48 32  -50 -67  71 58  -32 -6  25 -20  -12 37  82 -76  21 81  -53 -53  -19 -4  -77 37  -62 -40  -18 97  94 -95  -45 67
16 66
53 -52  -47 87  -82 61  -96 -38  -15 -16  51 -78  -35 25  -7 97  72 41  -23 -83  14 65  -45 74  97 -49  17 52  -44 -17  56 -91
18 66
59 46  -1 20  50 62  55 -67  -38 77  -52 87  -30 -56  58 61  -28 76  -26 87  81 98  83 83  15 34  89 48  -61 48  -71 99  -7 -22  -32 93
18 66
-78 76  -99 50  75 88  70 -82  -4 -20  -60 -79  4 -74  52 1  59 -16  66 -57  -27 -36  -18 -80  -7 -70  -36 21  -2 -94  -39 -29  83 -38  71 57
19 66
40 25  -4 -81  66 17  23 42  -82 74  -49 3  40 -6  76 -97  26 46  -54 57  -91 17  -96 -84  78 -75  49 -60  96 -45  -60 -15  80 36  -46 -5  -98 27
18 66
71 1  -62 -27  91 -18  99 44  -93 -5  40 14  4 -44  19 -30  -66 -6  69 -76  -10 -77  -36 25  54 50  80 -52  2 6  86 -28  57 -77  -4 47
4 66
-56 -60  -37 39  80 77  94 87
17 66
-87 71  40 83  95 -71  56 -92  4 9  8 -17  8 60  90 -7  82 -4  -33 -23  -57 22  22 -67  85 -90  -87 62  -97 100  -94 -83  20 46
18 66
14 25  55 -28  -71 -86  80 -38  22 -11  -99 65  -30 -2  -69 -2  41 54  70 74  -12 80  37 100  84 -14  -94 -100  -95 2  50 -31  78 -46  41 57
6 66
-30 -82  40 59  -80 5  -71 18  -14 27  -92 90
18 66
32 -22  -75 -31  -23 -92  5 -67  59 11  -14 -42  30 -37  13 -29  -81 31  41 -63  -79 -50  -93 -24  -71 25  62 56  33 52  -99 -85  80 -74  -16 -94
13 66
39 -60  44 100  26 -98  30 39  -35 -100  8 46  -9 45  67 -9  53 -58  20 -73  55 -25  11 6  -74 26
19 66
-47 60  -9 -62  -2 -19  32 -2  57 -16  -73 -55  -1 78  53 -55  -82 -2  62 10  -100 55  -71 -73  9 -45  -12 65  -19 -87  100 -16  73 -60  -28 -29  -28 -96
8 66
-72 -12  46 -26  88 -27  77 83  -9 -26  -6 -100  -76 -52  -70 -98
2 66
-15 -10  -29 16
3 66
-80 -100  -74 -39  -28 -3
3 66
-24 -85  11 15  11 35
7 66
84 12  85 -25  36 -22  -75 11  27 -45  13 84  -10 53
3 66
-94 -94  -75 57  -67 -64
6 66
30 19  -45 -4  -70 20  57 15  72 41  77 56
20 66
13 -67  91 74  10 97  -14 -6  -64 89  -1 93  96 -26  49 -72  11 28  8 -71  83 54  -91 2  11 -25  -77 -99  -49 29  67 14  62 7  -13 -78  -47 23  -34 -10
20 66
15 -18  7 89  82 35  -51 9  93 -71  -9 47  -62 43  -43 -37  16 -42  15 -56  75 79  -95 -69  -34 78  -15 89  -57 25  -50 58  57 57  -3 38  -59 46  -54 -66
15 66
-13 31  64 80  88 -74  -5 96  -9 39  20 -30  -5 1  -14 -28  86 -26  -34 -40  -25 74  -83 -69  -30 55  -77 67  52 -93
12 66
-62 38  4 69  25 -19  -37 -30  72 -98  90 -59  -53 -60  -23 19  -74 2  35 -64  77 9  -47 58

Output

Input

5 4
10 6  2 1  4 0  6 3  1 8
5 1
5 3  7 4  9 10  2 0  10 8
5 20
0 4  6 0  10 3  10 10  7 10
10 5
7 -1  -9 -3  6 6  5 8  2 4  10 0  10 -8  -8 5  7 9  -3 -2
10 10
-1 1  1 -9  0 -1  -4 1  2 7  -5 9  8 0  4 2  -7 -1  -7 7
8 66
-56 -35  11 -5  78 41  -100 -44  -95 -37  8 -38  7 -81  -73 -70
17 66
-28 -18  21 30  -82 5  16 -34  -3 40  30 -32  35 94  13 50  -46 -93  -23 96  58 -17  51 -79  91 63  28 60  41 8  -99 -88  91 -28
16 66
59 27  59 75  -77 -52  -46 -8  33 -53  55 -17  -48 62  10 -53  -31 94  98 -10  84 61  69 44  -49 -74  -5 -87  67 17  6 25
20 66
-36 -50  -83 12  4 9  96 52  -87 -22  54 25  88 -100  95 31  48 -16  15 -42  -98 -92  9 -71  -47 23  96 70  -72 -29  -87 -58  21 82  4 -76  -10 -1  26 4
5 66
-21 -72  -35 -71  73 96  78 -93  -40 86
10 66
-82 -5  89 -29  68 35  -59 46  -95 -96  88 -24  86 -59  -50 -74  -9 77  -20 68
5 66
-42 83  86 -69  79 13  -62 89  -2 98
7 66
43 87  -72 10  21 -31  -45 -24  -76 93  52 -91  85 -99
7 66
-25 28  -35 93  -16 -26  76 -31  5 4  32 -7  -8 -71
20 66
-51 73  -74 -22  -68 47  -3 -12  73 21  -70 24  31 -86  -24 -34  -61 54  32 -68  -63 -95  58 -44  -40 -39  88 53  53 68  93 53  -10 -81  -70 22  16 27  60 -61
10 66
91 13  29 55  89 95  45 -7  -24 27  -20 -69  -16 37  -9 45  -26 94  -53 92
8 66
100 -19  6 80  54 72  7 13  -90 5  -47 24  -67 -92  -38 78
6 66
55 -96  -21 -65  -65 13  22 -23  -43 46  -80 -46
20 66
57 -46  69 -38  84 22  85 -10  -65 95  45 -12  18 28  -54 81  6 49  -15 10  78 -30  -5 -10  92 72  -3 -12  43 52  -75 -1  56 44  12 39  -34 -4  80 -49
9 66
24 -11  59 -48  36 -11  8 -16  24 68  -38 95  -38 2  86 85  100 -27
4 66
51 -52  76 -44  93 -13  95 -92
17 66
24 -41  74 -52  48 32  -50 -67  71 58  -32 -6  25 -20  -12 37  82 -76  21 81  -53 -53  -19 -4  -77 37  -62 -40  -18 97  94 -95  -45 67
16 66
53 -52  -47 87  -82 61  -96 -38  -15 -16  51 -78  -35 25  -7 97  72 41  -23 -83  14 65  -45 74  97 -49  17 52  -44 -17  56 -91
18 66
59 46  -1 20  50 62  55 -67  -38 77  -52 87  -30 -56  58 61  -28 76  -26 87  81 98  83 83  15 34  89 48  -61 48  -71 99  -7 -22  -32 93
18 66
-78 76  -99 50  75 88  70 -82  -4 -20  -60 -79  4 -74  52 1  59 -16  66 -57  -27 -36  -18 -80  -7 -70  -36 21  -2 -94  -39 -29  83 -38  71 57
19 66
40 25  -4 -81  66 17  23 42  -82 74  -49 3  40 -6  76 -97  26 46  -54 57  -91 17  -96 -84  78 -75  49 -60  96 -45  -60 -15  80 36  -46 -5  -98 27
18 66
71 1  -62 -27  91 -18  99 44  -93 -5  40 14  4 -44  19 -30  -66 -6  69 -76  -10 -77  -36 25  54 50  80 -52  2 6  86 -28  57 -77  -4 47
4 66
-56 -60  -37 39  80 77  94 87
17 66
-87 71  40 83  95 -71  56 -92  4 9  8 -17  8 60  90 -7  82 -4  -33 -23  -57 22  22 -67  85 -90  -87 62  -97 100  -94 -83  20 46
18 66
14 25  55 -28  -71 -86  80 -38  22 -11  -99 65  -30 -2  -69 -2  41 54  70 74  -12 80  37 100  84 -14  -94 -100  -95 2  50 -31  78 -46  41 57
6 66
-30 -82  40 59  -80 5  -71 18  -14 27  -92 90
18 66
32 -22  -75 -31  -23 -92  5 -67  59 11  -14 -42  30 -37  13 -29  -81 31  41 -63  -79 -50  -93 -24  -71 25  62 56  33 52  -99 -85  80 -74  -16 -94
13 66
39 -60  44 100  26 -98  30 39  -35 -100  8 46  -9 45  67 -9  53 -58  20 -73  55 -25  11 6  -74 26
19 66
-47 60  -9 -62  -2 -19  32 -2  57 -16  -73 -55  -1 78  53 -55  -82 -2  62 10  -100 55  -71 -73  9 -45  -12 65  -19 -87  100 -16  73 -60  -28 -29  -28 -96
8 66
-72 -12  46 -26  88 -27  77 83  -9 -26  -6 -100  -76 -52  -70 -98
2 66
-15 -10  -29 16
3 66
-80 -100  -74 -39  -28 -3
3 66
-24 -85  11 15  11 35
7 66
84 12  85 -25  36 -22  -75 11  27 -45  13 84  -10 53
3 66
-94 -94  -75 57  -67 -64
6 66
30 19  -45 -4  -70 20  57 15  72 41  77 56
20 66
13 -67  91 74  10 97  -14 -6  -64 89  -1 93  96 -26  49 -72  11 28  8 -71  83 54  -91 2  11 -25  -77 -99  -49 29  67 14  62 7  -13 -78  -47 23  -34 -10
20 66
15 -18  7 89  82 35  -51 9  93 -71  -9 47  -62 43  -43 -37  16 -42  15 -56  75 79  -95 -69  -34 78  -15 89  -57 25  -50 58  57 57  -3 38  -59 46  -54 -66
15 66
-13 31  64 80  88 -74  -5 96  -9 39  20 -30  -5 1  -14 -28  86 -26  -34 -40  -25 74  -83 -69  -30 55  -77 67  52 -93
12 66
-62 38  4 69  25 -19  -37 -30  72 -98  90 -59  -53 -60  -23 19  -74 2  35 -64  77 9  -47 58

Output

Information

Author: PRO1
Language: Catalan
Official solutions: C++
User solutions: C C++ Python