10316 - Airline Hub

[sohel]

a line from problem statement:

Code: Select all

 They wish to place their central hub at the airport that minimizes the maximum direct flying distance from the hub to any other airport in the world.

but you are adding all the distances from a reference point..

replace
totDist += dist[j];
with
totDist = max( totDist, dist[j] ).

and you should get Ac.

[arif_pasha]

Thanks Sohel.. .. got ac now..

[sis655]

Hallo i have got always Wrong Answer but I do not know what is wrong ? Can somebody help me ?

My code :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define pi 3.14159265358979323846

double vys[1][2];
double pii = pi /180;


double delka(double lat1, double lon1,double lat2,double lon2)
{
double dist;
dist = acos(sin((lat1)* pii)
* sin((lat2)* pii)
+ cos((lat1)* pii)
* cos((lat2)* pii)
* cos((lon1 - lon2)* pii));
/*printf("Vzdalenost %lf\n",dist);*/
return dist;
}

int main()
{
int pocet,i,j,a;
double min,maximum;

a=1;

while(scanf("%d",&pocet)!=EOF){
double let[pocet][2]; /* 1 a 2 sirka a delka */
double max[pocet];

for(i=0;i<pocet;i++){
scanf("%lf %lf",&let[0],&let[1]);
}

/* Ulozeni vzdalenosti do pole */
for(i=0;i<pocet;i++){
max=0;
for(j=0;j<pocet;j++){
if(i!=j){
maximum = delka(let[0],let[1],let[j][0],let[j][1]);
if(max < maximum || fabs(maximum - max) < 1e-6 ){ /* bez epsilon check */
max = maximum;
}
}
}
}

min = max[pocet-1];
for(i=pocet-2;i>=0;i--){
if(min > max || fabs(min - max) < 1e-6){
min = max[i];
vys[0][0] = let[i][0];
vys[0][1] = let[i][1];
}
}
a++;
printf("%.2lf %.2lf",vys[0][0],vys[0][1]);
if(a!=pocet) printf("\n");
}
return 0;
}

[helloneo]

hello..~
i really don't understand..

is this formular wrong..?
or am i misunderstanding this problem..?

i don't even get correct output for sample input..
please help me.. ; ㅜ.ㅜ

Code: Select all

code removed

[arif_pasha]

Your formula for calculating distance is correct.

however, did u converted the angles from degree to radian?

[helloneo]

Your formula for calculating distance is correct.

however, did u converted the angles from degree to radian?

Thanks for help..
I got AC..

It was really stupid mistake..

[Sedefcho]

Can someone post several sample test case I/O ?
Thanks in advance.

[Sedefcho]

Can someone post several sample test case I/O ?
Thanks in advance.

[Shafaet_du]

Be careful about precision when comparing. Dont directly check equality of Doubles,use epsilon.i used 1e-8 and long double.

[ujjal.ruet]

I am getting TLE on this problem.Can anyone help me to improve running time????
Thanks in advance..

Code: Select all

////10316 Airlines HUB//////

#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAXN 1002
#define RADIO 6378.0
#define INF 2147483647

double PIx=3.141592653589793;



int n;


long myRound(double x)
{

return (long)(x+0.5f);
}


double radianes(double x)
{
return x * PIx / 180;
}




long cost(double la1,double lo1,double la2,double lo2){

double lon2 =radianes(lo2);
double lon1 =radianes(lo1);
double lat2 =radianes(la2);
double lat1 =radianes(la1);

double dlon = lon2 - lon1;
double dlat = lat2 - lat1;
double a = (sin(dlat/2)*sin(dlat/2)) + cos(lat1) * cos(lat2) * (sin(dlon/2)*sin(dlon/2));
double angulo = 2 * atan2(sqrt(a), sqrt(1-a));


return (myRound(angulo*RADIO));

}






int main(){


int i,j,k,m,q,l,p=1;
long A[MAXN],min;

double lat[MAXN],lon[MAXN],res;

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

for(i=0;i<n;i++)
scanf("%lf %lf",&lat[i],&lon[i]);




for(i=0;i<n;i++){
res=0;
 for(j=0;j<n;j++)
     res+=cost(lat[i],lon[i],lat[j],lat[j]);

A[i]=res/n;
}

k=0;
min=A[0];
for(i=1;i<n;i++)
      if(A[i]<=min){
           min=A[i];
           k=i;
           }

printf("%.2lf %.2lf\n",lat[k],lon[k]);
}
return 0;
}

[ujjal.ruet]

On my last code after using !=EOF i got Wrong answer.Anyone,please help me.