#include<stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define distance(xi,xj,yi,yj) sqrt(pow((xi)-(xj),2.0)+pow((yi)-(yj),2.0))
#define MaxN 100
 
FILE *fp1;
FILE *fp2;
FILE *fp3;
 
struct CityInfo
{
    int citynumber;
    double x;
    double y;
};
 
int main(void){
int N;
int n;
int city_number;
double a, b;
    double ux;
    double uy;
 
    struct CityInfo cityinfo[MaxN]{{ 0, 0.0, 0.0 }};
 
 
    printf("訪問都市の位置座標x座標とy座標の範囲(下限a,上限b)の設定について\n");
    printf("範囲の下限aを指定して下さい____> "); scanf_s("%lf", &a);
    printf("範囲の上限bを指定して下さい____> "); scanf_s("%lf", &b);
    printf("訪問都市数Nを指定して下さい____>"); scanf_s("%d", &N);
 
    errno_t err, err_r;
    err = fopen_s(&fp1, "citydata_info.csv", "w");
    if (err == 1)
    {
        printf("The file 'citydata_info.csv'was not opened\n\n");
    }
 
    srand((unsigned int)time(NULL));
 
    printf("\n都市番号\tx座標\t\t\ty座標\n");
 
    for (n = 1; n <= N; n++) {
        
        city_number = n;
 
        ux = (double)rand() / (double)RAND_MAX;
        cityinfo[n].x = a + (b - a) * ux;
        uy = (double)rand() / (double)RAND_MAX;
        cityinfo[n].y = a + (b - a) * uy;
        
        
        printf("%d\t\t%lf\t\t%lf\n", n, cityinfo[n].x, cityinfo[n].y);
        fprintf(fp1, "%d\t%lf\t%lf\n", n, cityinfo[n].x, cityinfo[n].y);
 
    }
 
    if (fp1)
    {
        err = fclose(fp1);
        if (err == 1)
        {
            printf("The file 'citydata_info.csv'was not closed\n\n");
        }
    }
 
 
    struct CityInfo *cityinfodata;
 
    cityinfodata = (struct CityInfo *)malloc((N + 1) *sizeof(struct CityInfo ));
    if (cityinfodata == NULL){
        printf(" メモリが確保できません。\n"); exit(1);
    }
 
    for (n = 0; n <= N; n++){
        cityinfo[n].citynumber = 0;
        cityinfo[n].x = 0.0;
        cityinfo[n].y = 0.0;
    }
    if (err == 1){
        printf("The file 'citydata_info.txt' was not opened as read mode.\n\n");
    }
    err_r = fopen_s(&fp2, "citydata_info.csv", "w");
 
    if (err_r == 1){
        printf("The file 'citydata_info.csv' was not opened as read mode.\n\n");
    }
 
    n = 0;
 
    while ((fscanf_s(fp1, "%d,%lf,%lf", &cityinfo[n].citynumber, &cityinfo[n].x, &cityinfo[n].y)) == 3){
 
        fprintf_s(fp2, "%d,%lf,%lf\n", cityinfo[n].citynumber, cityinfo[n].x, cityinfo[n].y);
 
        n++;
 
    }
    
 
    if (fp1){
        err = fclose(fp1);
        if (err == 1){ printf("The file 'citydata_info.txt' was not closed.\n\n"); }
    }
    if (fp2){
        err_r = fclose(fp2);
        if (err_r == 1){ printf("The file 'citydata_info.csv' was not closed.\n\n"); }
    }
 
    err_r = fopen_s(&fp2, "citydata_info.csv", "r");
 
    if (err_r == 1){
        printf("The file 'citydata_info.csv' was not opened as read mode.\n\n");
    }
 
    errno_t err3;
    err3 = fopen_s(&fp3, "qwerty.csv", "w");
    if (err3 == 1)
    {
        printf("The file qwerty.csv' was not opened as read mode.\n\n");
    }
    fprintf_s(fp3, "都市番号,x座標,y座標\n");
 
    while ((fscanf_s(fp3, "%d,%lf,%lf", &cityinfo[n].citynumber, &cityinfo[n].x, &cityinfo[n].y)) == 3){
 
        n++;
 
    }
 
    int *z;
    z = (int *)malloc((N + 1) *sizeof(int));
    if (z == NULL){
        printf("一次元配列 z のメモリを確保できません。\n"); exit(1);
    }
 
    for (n = 0; n <= N; n++){
        z[n] = 0;
    }
 
    int *zz;
    zz = (int *)malloc((N + 1) *sizeof(int));
    if (zz == NULL){
        printf("一次元配列 zz のメモリを確保できません。\n"); exit(1);
    }
 
    for (n = 0; n <= N; n++){
        zz[n] = 0;
    }
    
    clock_t start_time, end_time;
    int start;
    int i;
    int j;
    int k;
    int next;
    double min;
    double disij;
    double tdis=0.0;
    
    start = 0;
    printf("\n最初の出発都市startを都市番号1～%dより指定してください。-->", N); scanf_s("%d", &start);
 
    start_time = clock();
    i = start;
 
    printf("k\ti\tnext\tmin\ttdis\n");
    
    k = 1;
 
    
    z[i] = k;
    zz[k] = i;
 
    for (k = 2; k <= N; k++) {
        min = 10000.0;
        for (j = 1; j <= N ; j++) {
            if (z[j] == 0) {
                disij = distance(cityinfo[i].x, cityinfo[j].x, cityinfo[i].y, cityinfo[j].y);
 
                if (disij<min) {
                    next = j;
                    min = disij;
                }
            }
        }
        
        z[next] = k;
        zz[k] = next;
        tdis = tdis + disij;
        i = next;
        
        printf("%d\t%d\t%d\t%lf\t%lf\n", k, i, next, min, tdis);
        fprintf(fp3, "%d,%d,%d,%lf,%lf\n", k, i, next, min, tdis);
 
    }
 
    end_time = clock();
 
    double ldis= 0.0;
    ldis = sqrt(pow(cityinfo[start].x - cityinfo[next].x, 2.0) + pow(cityinfo[start].y - cityinfo[next].y, 2.0));
    tdis = tdis+ldis;
    
    printf("\t%d\t%d\t%lf\t%lf\n", next, start, ldis, tdis);
    fprintf(fp3, ",%d,%d,%lf,%lf\n", next, start, ldis, tdis);
 
    double searching_time;
    searching_time = (double)(end_time - start_time) / (double)CLOCKS_PER_SEC;
 
    printf("\n最近隣法による最短巡回経路の総移動距離は%lfです。\n", tdis);
    fprintf_s(fp3, "\n最近隣法による最短巡回経路の総移動距離は%lfです。\n", tdis);
 
    printf("探索処理時間%lf秒\n", searching_time);
    fprintf_s(fp3, "探索処理時間%lf秒\n", searching_time);
 
    free(cityinfo);
    free(z);
    free(zz);
 
    return 0;
}