## 10316 - Airline Hub

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### overlooked..

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
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:
Thanks Sohel.. .. got ac now..

sis655
New poster
Posts: 1
Joined: Sun Feb 12, 2006 3:26 pm

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
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..

Code: Select all

``````code removed
``````
Last edited by helloneo on Sat May 06, 2006 4:04 am, edited 1 time in total.

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:
Your formula for calculating distance is correct.

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

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
arif_pasha wrote: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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Can someone post several sample test case I/O ?

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Can someone post several sample test case I/O ?

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

### Re: 10316 - Airline Hub

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

ujjal.ruet
New poster
Posts: 15
Joined: Thu Sep 02, 2010 3:10 pm
Contact:

### Re: 10316 - Airline Hub

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

Code: Select all

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

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

double PIx=3.141592653589793;

int n;

long myRound(double x)
{

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

{
return x * PIx / 180;
}

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

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));

}

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
New poster
Posts: 15
Joined: Thu Sep 02, 2010 3:10 pm