Theory: Distance This uses the ‘haversine’ formula to calculate the great-circle distance between two points – that is, the shortest distance over the earth’s surface – giving an ‘as-the-crow-flies’ distance between the points (ignoring any hills they fly over, of course!). Haversine formula: a = sin²(Δφ/2) + cos φ1 * cos φ2 * sin²(Δλ/2) c = 2
Category: Algorithm
10409
#include <iostream> #include <cstring> #include <string> #include <vector> #include <fstream> #include <map> #define INF 1000000000 using namespace std; int T,B,W,E,S,N; int Prev_T,Prev_N,Prev_B,Prev_S,Prev_W,Prev_E; int main() { int n; string cmd; while(cin>>n) { if(n==0) break; T=1;N=2;W=3; B=6;S=5;E=4; while(n–) { cin>>cmd; if(cmd=="north") { Prev_T=T;Prev_N=N;Prev_B=B;Prev_S=S; Prev_W=W;Prev_E=E; T = Prev_S; N = Prev_T;W=Prev_W; B = Prev_N;S=Prev_B;E=Prev_E; } else if(cmd=="south") {
10171
#include <iostream> #include <string.h> #include <vector> #include <fstream> #include <map> #define INF 1000000000 using namespace std; int grY[30][30]; int grO[30][30]; int main() { int N,KK,st,dst; char people,roadtyp,ct1,ct2; char start,dest; int energy; // ofstream out; // out.open("out.txt"); while(cin>>N) { if(N==0) break; for(int i=0;i<30;i++) { for(int j=0;j<30;j++) { if(i==j) { grY[i][j]=0; grO[i][j]=0; } else { grY[i][j]=INF; grO[i][j]=INF;
10269
This can be done two ways using floyed-warshall algorithm and also using bfs; Floyed warshall: #include <iostream> #include <queue> #include <cstring> #define INF 1500000 using namespace std; int gr[105][105]; int A,B,M,L,K; bool trace[105][15]; int d[105][15]; int shortestpath() { d[A+B][0]=0; queue<int> q; q.push(A+B); q.push(0); //trace[A+B][0]=1; while(!q.empty()) { int a = q.front();q.pop(); int boot = q.front();q.pop(); trace[a][boot]=0;
571
#include <iostream> #include <queue> #include <string.h> #include <map> #include <vector> #define EmA 3 #define EmB 4 #define FilA 1 #define FilB 2 #define PorAB 5 #define PorBA 6 using namespace std; struct point{ int x; int y; }; point inp,rp,tmp; int gr[1002][1002]; int work[1002][1002]; point par[1002][1002]; vector<int> vb; int A,B,C; void path(point p) { int
104
#include <iostream> #define FOR(i,n) for(int i=1;i<=n;i++) double gr[22][22][22]; int nxt[22][22][22]; int backtrck[22]; int n; using namespace std; int path(int step,int i,int j) { backtrck[step] = j; step-=1; while(step) { backtrck[step]=nxt[step][i][j]; step-=1; j= nxt[step][i][j]; } backtrck[step]=nxt[step+1][i][j]; return 0; } void init() { FOR(step,n) FOR(i,n) FOR(j,n) { nxt[1][i][j]=i; gr[step][i][j]=0; } } int main() { while(cin>>n) { init();
423
#include <iostream> #include <string.h> #define FOR(i,n) for(int i=1;i<=n;i++) #define INF 1<<29 using namespace std; int gr[101][101]; int main() { int n,MN; string a; while(cin>>n) { MN = INF; FOR(i,n) { FOR(j,n) { gr[i][j]=INF; if(i==j) gr[i][j]=0; } } for(int i=2;i<=n;i++) { for(int j=1;j<i;j++) { cin>>a; if(a=="x") gr[i][j]=gr[j][i]=INF; else { int t=0; for(int x=0;x<a.size();x++) { t =
10246
#include <iostream> #define INF 100000000 using namespace std; int graph[85][85]; int feast[85][85]; int main() { int C,R,Q; int a,b,c; int kase=0; while(cin>>C) { cin>>R>>Q; if(C==0 && R==0 && Q==0) break; for(int i=1;i<=C;i++) { for(int j=1;j<=C;j++) { if(i==j) graph[i][j] = 0; else graph[i][j] = feast[i][j]=INF; } } for(int i=1;i<=C;i++) { int g; cin>>g; feast[i][i]=g; } for(int
523
#include <iostream> #include <sstream> #include <string> #include <string.h> #include <stdio.h> #define INF 10000000 using namespace std; int graph[105][105]; int tax[105]; int nxt[105][105]; int par[105]; int cnt; int path(int i,int j) { cout<<"Path: "; if(i==j) { cout<<i<<"–>"<<j<<"\n"; return 0; } cout<<i<<"–>"; while(i!=j) { i=nxt[i][j]; if(i==j) cout<<i; else cout<<i<<"–>"; } cout<<"\n"; return 0; } int main() {
10085
#include <iostream> #include <string.h> #include <string> #include <vector> #define MX 1000003 using namespace std; int kase = 1; int in[9]; int visit[MX]; int next[MX]; int par[MX]; char val[MX]; int num[MX][9]; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; vector<int> vb[MX]; string s; int GetHash(int *arr) { int h=0; for(int i=0;i<9;i++) { h=h*10+arr[i]; } h=h%MX; return h; } bool isNew(int *arr,int pos)