HeatEquationSolver/task2.cpp at main · Emipano/HeatEquationSolver · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

struct punto {
    int n, i, j;
    double x, y;
};

// funzione ricorsiva per nested dissection
vector<int> ordina(vector<punto> punti, bool dir_x) { // se dir_x è true taglia lungo x, altrimenti lungo y

    if (punti.size()<=1) { // caso base
        vector<int> indici;
        if (punti.size()==1) { // se c'è un punto lo metto nel vettore, se non c'è il vettore rimane vuoto
            indici.push_back(punti[0].n);
        }
        return indici;
    }

    // caso ricorsivo

    // riordinamento lungo x o y
    if (dir_x) {
        sort(punti.begin(), punti.end(), [](punto a, punto b) {
        return a.x < b.x;   // ordina per x crescente
        });
    }
    else {
        sort(punti.begin(), punti.end(), [](punto a, punto b) {
        return a.y < b.y;  // ordina per y crescente
        });
    }

    // ricerca del separatore
    int indice_mediano = punti.size()/2;
    double separatore;
    punto mediano = punti[indice_mediano];

    if (dir_x) {
        separatore = mediano.x;
    }
    else {
        separatore = mediano.y;
    }

    // taglio
    vector<punto> V1;
    vector<punto> V2;
    vector<punto> VS;

    for (const punto& p : punti) {
        if (dir_x) { // taglio su x
            if (p.x<separatore) {
                V1.push_back(p);
            }
            if (p.x>separatore) {
                V2.push_back(p);
            }
            if (p.x==separatore) {
                VS.push_back(p);
            }
        }
        else {  //talgio su y
            if (p.y<separatore) {
                V1.push_back(p);
            }
            if (p.y>separatore) {
                V2.push_back(p);
            }
            if (p.y==separatore) {
                VS.push_back(p);
            }
        }
    }
    // chiamata ricorsiva
    vector<int> lista1 = ordina(V1, !dir_x); // inverte direzione con !
    vector<int> lista2 = ordina(V2, !dir_x);

    vector<int> ordine = lista1;
    for (int x : lista2) {
        ordine.push_back(x);
    }
    for (const punto& p : VS) {
        ordine.push_back(p.n);
    }

    return ordine;

}

int main() {

    // lettura coords.txt
    int n, i, j;
    double x, y;
    vector<punto> punti;

    ifstream fileCoord("coords.txt");

    while (fileCoord>>n>>i>>j>>x>>y) {

        punto P;

        P.n = n;
        P.i = i;
        P.j = j;
        P.x = x;
        P.y = y;

        punti.push_back(P);
    }

    // ordinamento
    vector<int> ordinamento = ordina(punti, true);

    // scrittura file ordering.txt
    ofstream fileOrder("ordering.txt");
    for (int m = 0; m < ordinamento.size(); m++) {
        fileOrder << m << " " << ordinamento[m] << endl;
    }
    fileOrder.close();

    return 0;
}