1451.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1451 on 2005-10-13 at 11:42:45 */ 
#include <cstdio>
#include <cstring>
#include <cmath>
#define  MAX  32
#define  MAX_CITY  128
#define  EARTH_R  6378

class City {
public:
	char name[MAX];
	double lati;
	double longi;
	City *left;
	City *right;
	void init(char *s, double lat, double lon) {
		left = NULL;
		right = NULL;
		lati = lat;
		longi = lon;
		strcpy(name, s);
	}
	void add(City *node) {
		City *p = this;
		int i;
        while(true) {
            i = strcmp(node->name, p->name);
            if(i < 0) {
                if(p->left != NULL) {
                    p = p->left;
                } else {
                    p->left = node;
                }
            } else if(i > 0) {
                if(p->right != NULL) {
                    p = p->right;
                } else {
                    p->right = node;
                }
            } else {
				return;
            }
        }
	}
	City* search(char *s) {
		City *p = this;
		int i;
		while(true) {
            i = strcmp(s, p->name);
            if(i < 0) {
                if(p->left != NULL) {
                    p = p->left;
                } else {
                    return NULL;
                }
            } else if(i > 0) {
                if(p->right != NULL) {
                    p = p->right;
                } else {
                    return NULL;
                }
            } else {
				return p;
            }
        }
	}
};

double distance(City*, City*);

int main()
{
	char name[MAX], line[1024], nameA[MAX], nameB[MAX];
	City city[MAX_CITY], *root, *ca, *cb;
	int n;
	double longi, lati;
	
	while(true) {
		root = NULL;
		for(n = 0; ; n++) {
			if(gets(line) == NULL) {
				return 0;
			} else {
				if(!strcmp(line, "#")) {
					break;
				} else {
					sscanf(line, "%s %lf %lf", name, &lati, &longi);
					city[n].init(name, lati, longi);
					if(root == NULL) {
						root = &city[n];
					} else {
						root->add(&city[n]);
					}
				}
			}
		}
		while(true) {
			gets(line);
			if(!strcmp(line, "# #")) {
				break;
			} else{
				sscanf(line, "%s %s", nameA, nameB);
				printf("%s - %s\n", nameA, nameB);
				ca = root->search(nameA);
				cb = root->search(nameB);
				if(ca == NULL || cb == NULL) {
					printf("Unknown\n");
				} else {
					printf("%.0lf km\n", distance(ca, cb));
				}
			}
		}
	}
	
	return 0;
}

double distance(City *a, City *b)
{
	double i, j, cosB;
	double xa, ya, za, xb, yb, zb;
	double d;
		
	i = a->longi * M_PI / 180;
	j = a->lati * M_PI / 180;
	cosB = cos(j);
	xa = EARTH_R * cos(i) * cosB;
	ya = EARTH_R * sin(i) * cosB;
	za = EARTH_R * sin(j);
	i = b->longi * M_PI / 180;
	j = b->lati * M_PI / 180;
	cosB = cos(j);
	xb = EARTH_R * cos(i) * cosB;
	yb = EARTH_R * sin(i) * cosB;
	zb = EARTH_R * sin(j);
	d = sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb)+(za-zb)*(za-zb));
	if(fabs(d) < 1e-3) {
		return 0;
	} else if(fabs(d-EARTH_R*2) < 1e-3) {
		return EARTH_R * M_PI;
	} else {
		return EARTH_R * 2 * asin(d/(EARTH_R*2));
	}
}