UVA 10075 solution C++ Code

Another all pairs shortest path problem. The most difficult part is in determining the shortest distance on a sphere (earth). It is hard to solve this problem without knowing the formula, please refer to my computational geometry section to find out the formula. With this formula, the rest is solvable using Floyd Warshall.



Code: 

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<iostream>
#include<vector>

#define MAXN 102
#define RADIO 6378.0
#define INF 2147483647


#define myRound(x) ( x 0.5f )
#define radianes(x) ( x * PIx / 180 )
#define ra(x) radianes(x)

#define cost(la1,lo1,la2,lo2) (myRound( ( 2 * atan2(sqrt( (sin( (ra(la2) - ra(la1) ) /2)*sin((ra(la2) - ra(la1))/2))   cos(ra(la1)) * cos(ra(la2)) * (sin((ra(lo2) - ra(lo1))/2)*sin((ra(lo2) - ra(lo1))/2)) ), sqrt(1- ((sin((ra(la2) - ra(la1))/2)*sin((ra(la2) - ra(la1))/2))   cos(ra(la1)) * cos(ra(la2)) * (sin((ra(lo2) - ra(lo1))/2)*sin((ra(lo2) - ra(lo1))/2)) ) ) ) )*RADIO ) )

using namespace std;

double PIx=3.141592653589793;
double lon2,lon1,lat2,lat1,dlon,dlat,a1,angulo;


vector< vector < long > > A(102,vector<long>(102));

map < string,int > ma;

int n;

inline void Ini() {
int i,j;
for(i = 1; i<=n; i  ){
for(j = i 1; j <=n; j  )
A[i][j]=A[j][i]=INF;
A[i][i]=0;
}
}

inline void floyd() {
int i, j, k;
for(k = 1; k <= n; k   ) {
for(i = 1; i <= n; i  ) {
for(j = 1; j<=n; j   ) {
if ((A[i][k] * A[k][j] != 0) && (i != j)&& A[i][k]!=INF && A[k][j]!=INF)
if ((A[i][k]   A[k][j] < A[i][j]) ||(A[i][j] ==0))
A[i][j]= A[i][k]   A[k][j];

}
}
}
}


int main(){


int i,j,k,m,q,l,p=1;


double lat[101],lon[101];
char a[21],b[21];

while(scanf("%d %d %d",&n,&m,&q)&&n&&m&&q){

Ini();

for(i=1;i<=n;i  ){
scanf("%s %lf %lf",a,&lat[i],&lon[i]);
ma.insert(make_pair(a,i));
}


for(i=1;i<=m;i  )
{
scanf("%s %s",a,b);

k=ma[a];
l=ma[b];

A[k][l]=cost(lat[k],lon[k],lat[l],lon[l]);

}


if(p>1)
printf("\n");

printf("Case #%d\n",p  );


floyd();


for(i=1;i<=q;i  )
{
scanf("%s %s",a,b);

k=ma[a];
l=ma[b];

if(A[k][l]==INF)
printf("no route exists\n");
else
printf("%ld km\n",A[k][l]);
}

ma.clear();

}

return 0;
}

UVA 12036 algorithm and solution C++ Code

All we need to check is whether an element in more than N times or not in the whole list. If does then the answer is true or else false.

For clarification see the following arrangement of 4*4 array. An element can only be at most four times to keep the grid stable. If it is five times then there is no place to put the extra element avoiding repetition .

1  x  x  x
x  1  x  x
x  x  1  x
x  x  x  1

Code:


#include<stdio.h>

int main(){

    int i,m,n,num,t,k,f;
    int frq[102]={0};

    scanf("%d",&t);

    k=0;
    while(++k<=t){

        scanf("%d",&n);

        m=n*n;
        f=1;
        for(i=101;i--;){
        frq[i]=0;
        }


        for(i=m ;i>0;i-- ){
        scanf( "%d", &num);
        frq[num]++;
              if( frq[num]>n ){f=0; break;}
        }
        i--;
        while(i>0){
        scanf( "%d", &num);
        i--;
        }

        if(f) printf("Case %d: yes\n",k);
        else  printf("Case %d: no\n",k);
    }

 return 0;
}

UVA 113 solution C++ Code

Code:

#include&amp;lt;stdio.h&amp;gt;
#include&amp;lt;math.h&amp;gt;

int main()
{

   double n,p;
   while(scanf(&amp;quot;%lf %lf&amp;quot;,&amp;amp;n,&amp;amp;p)!=EOF){
       printf(&amp;quot;%.0lf\n&amp;quot;,exp(log(p)/n));
   }

return 0;
}