Programozás‎ > ‎Feladatok‎ > ‎Gyalogtúra‎ > ‎Megoldás‎ > ‎

mb_tura.cpp

Letöltés: mb_tura.cpp

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
 
#define n 3137
#define N 3200
#define r 6367.5
#define pi 3.14159265
 
using namespace std;
void doit(int s, int f);
 
struct varos_struct
{
    char nev [50];
    float latitude;
    float longitude;
    int el [n];
    int el_darab;
};
 
int m;
 
varos_struct* varosok;
 
bool van_el [n][n];
 
void beolvas(char* fn)
{
    FILE* reader = fopen(fn, "r");
    varosok = new varos_struct[n];
    for(int i=0; i<n; i++)
    {
        fscanf(reader, "%s %f %f", &varosok[i].nev, &varosok[i].latitude, &varosok[i].longitude);
        varosok[i].latitude*=pi/180;
        varosok[i].longitude*=pi/180;
    }
    fclose(reader);
}
 
void beolvas_2(char* fn)
{
    FILE* reader = fopen(fn, "r");
    fscanf(reader, "%d", &m);
 
    char v1 [50];
    char v2 [50];
    int v1_id;
    int v2_id;
    for(int i=0; i<m; i++)
    {
        v1_id=-1;
        v2_id=-1;
        fscanf(reader, "%s %s", &v1, &v2);
        for(int j=0; j<n; j++)
        {
            if(strcmp(v1, varosok[j].nev)==0)
                v1_id=j;
 
             if(strcmp(v2, varosok[j].nev)==0)
                v2_id=j;
        }
 
        if(v1_id!=v2_id && v1_id!=-1 && v2_id!=-1)
        {
            doit(v1_id, v2_id);
        } else
        {
            printf("fuuu %d %d\n", v1_id, v2_id);
        }
    }
 
    fclose(reader);
}
 
float tavolsag(int f_id, int s_id)
{
    varos_struct f=varosok[f_id];
    varos_struct s=varosok[s_id];
    float szamalo =
    sqrt(
    pow((cos(f.latitude) * sin(s.longitude-f.longitude)),2)+
    pow((cos(s.latitude) * sin(f.latitude)-sin(s.latitude)*cos(f.latitude)*
    cos(s.longitude-f.longitude)), 2));
 
    float nevezo =
    sin(s.latitude)*sin(f.latitude)+cos(s.latitude)*cos(f.latitude)*cos(s.longitude-f.longitude);

    return r*atan2(szamalo, nevezo);
}
 
void process_map()
{
    for(int i=0; i<n; i++)
        varosok[i].el_darab=0;
    for(int i=0; i<n; i++)
    {
        if(i%10==0) printf("I: %d\n", i);
        for(int j=i; j<n; j++)
            if(i!=j && tavolsag(i, j)<=20)
            {
                van_el[i][j]=true;
                varosok[i].el[varosok[i].el_darab++]=j;
 
                van_el[j][i]=true;
                varosok[j].el[varosok[j].el_darab++]=i;
            }
    }
 
}
 
void doit(int s, int f)
{
    printf("Doing: %d %d (%s %s)\n", s, f, varosok[s].nev, varosok[f].nev);
    bool visited [N];
    int lista [N];
    int melyseg [N];
    int apa [N];
    for(int i=0; i<N; i++)
    {
        lista[i]=-1;
        apa[i]=-1;
        visited[i]=false;
        melyseg[i]=-1;
    }
 
    lista[0]=s;
    apa[s]=s;
    visited[s]=true;
    melyseg[s]=0;
    int at=0;
    int ir=1;
    while(lista[at]!=-1)
    {
        int current = lista[at];
        at++;
 
        for(int i=0; i<varosok[current].el_darab; i++)
        {
            int current2=varosok[current].el[i];
            if(!visited[current2])
            {
                visited[current2]=true;
                apa[current2]=current;
                melyseg[current2]=melyseg[current]+1;
                lista[ir++]=current2;
            }
        }
    }
 
    int a=f;
    printf("Melyseg: %d\n", melyseg[a]);
    while (a!=s && a!=-1)
    {
        printf("%s ", varosok[a].nev);
        a=apa[a];
    }
    printf("%s", varosok[s].nev);
 
    return;
}
 
int main()
{
    beolvas("magyarorszag.csv");
    process_map();
    beolvas_2("tura.be");
}