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

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

overlooked..

Post by sohel » Wed Sep 14, 2005 12:59 pm

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:

Post by arif_pasha » Wed Sep 14, 2005 9:56 pm

Thanks Sohel.. :D :D .. got ac now..

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

10316 WA please help :(.

Post by sis655 » Sun Feb 12, 2006 3:29 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

Post by helloneo » Thu May 04, 2006 4:37 pm

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
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:

Post by arif_pasha » Fri May 05, 2006 9:50 pm

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

Post by helloneo » Sat May 06, 2006 4:20 am

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..

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sat Feb 24, 2007 8:36 pm

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

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sat Feb 24, 2007 8:37 pm

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

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

Re: 10316 - Airline Hub

Post by Shafaet_du » Tue Nov 02, 2010 10:37 pm

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
Location: Dhaka,Bangladesh
Contact:

Re: 10316 - Airline Hub

Post by ujjal.ruet » Fri Jan 14, 2011 6:45 pm

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

Re: 10316 - Airline Hub

Post by ujjal.ruet » Fri Jan 14, 2011 6:49 pm

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

Post Reply

Return to “Volume 103 (10300-10399)”