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

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

10316 - Airline Hub

Post by Joe Smith » Sat Jul 06, 2002 7:45 am

I keep getting WA and this is such a simple problem. My solution works fine on the judge's data from the original Waterloo contest, and my solution is basically identical to theirs (modified to take multiple cases and return the last airport if there's a tie).

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

No

Post by shahriar_manzoor » Sat Jul 06, 2002 11:00 am

Compare the problem statement of Waterloo contest and 50th contest. There is a slight difference :)

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

Re: No

Post by Joe Smith » Sat Jul 06, 2002 5:08 pm

shahriar_manzoor wrote:Compare the problem statement of Waterloo contest and 50th contest. There is a slight difference :)
Thanks. The problem was a roundoff error... I added an epsilon check and got AC.

But I don't understand why floating point tricks like this have to be introduced, they have nothing to do with the original problem and are just annoying. There's a reason the Waterloo version allowed any solution to be returned instead of insisting on the last (or first) one. Oh well.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Reply

Post by shahriar_manzoor » Sat Jul 06, 2002 5:37 pm

Well, they accepted any solution but the solution checker was not online. So either I had to write the solution checker or I had to put such a restriction that would allow us to accept unique answers. I chose the easier one :wink: Before implementing i didn't know that an epsilon had to be added, I learnt it after I modified the code and found that it was not working without epsilon. This change also prevented (during contest) anyone to submit the solution from waterloo site.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

10316 Airline Hub

Post by .. » Fri Jul 12, 2002 7:30 pm

Is there any O(nlgn) algorithm for this question?
I find that my O(n^2) algorithm is quite slow when compared to other people on ranklikst.

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Fri Jul 12, 2002 10:21 pm

I'm not sure about a solution better than n^2. In your distance formula are you using acos() or sqrt()? You don't need to. Or perhaps are you repeating the conversion from spherical to cartesian coordinates?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Jul 13, 2002 7:30 am

Oh yes, I use a acos in my program, after removing it,
my program runs much faster, thanks!! :D

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

10316 - Airline Hub - Please help

Post by Dominik Michniewski » Fri Nov 22, 2002 10:40 am

Could anyone help me with this problem ?

I solved looks like this problem "Globtrotter" (5xx), but I got WA now ...
I think, that I must make some stupid mistake ...

I use folowing code:

Code: Select all

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

#define MAX 1001
#define PI 3.141592653589793
#define RAD (PI/180.0)

typedef struct _point { double x,y,z; } POINT;

POINT c[MAX];
double cities_in[MAX][2];

int main(void)
{
	int N,i,min_i,j;
	double cos_psi,longitude,latitude,min,act,p;

	while(scanf("%d",&N) == 1)
	{
		for(i=0;i<N;i++)
		{
			scanf("%lf %lf",&latitude,&longitude);
			cos_psi = cos(latitude*RAD);
			c[i].x = cos_psi*cos(longitude*RAD);
			c[i].y = cos_psi*sin(longitude*RAD);
			c[i].z = sin(latitude*RAD);
			cities_in[i][0] = latitude;
			cities_in[i][1] = longitude;
		}
		min = -1.0;
		for(i=0;i<N;i++)
		{
			act = 1.0;
			for(j=0;j<N;j++)
			{
				p = c[i].x*c[j].x + c[i].y*c[j].y + c[i].z*c[j].z;
				if(p < act) act = p;
			}
			if(act >= min)
			{
				min = act;
				min_i = i;
			}
		}
		printf("%.2lf %.2lf\n",cities_in[min_i][0],cities_in[min_i][1]);
	}
	return 0;
}

Thank all for help or some test cases ...

Regards
Dominik

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Fri Nov 22, 2002 2:55 pm

AFAIR, there was a thread about this problem earlier. You're need to use epsilon to compare floating point values.

Bistromath
New poster
Posts: 16
Joined: Fri Oct 11, 2002 11:03 pm
Location: France

Post by Bistromath » Fri Nov 22, 2002 8:46 pm

Hi,

I don't know if your formula is correct but in my solution (got AC) i do not convert from (latitude,longitude) to 3D coordinates. I directly compute the distance on the great arc using latitude and longitude with the following formula (no need for epsilon) :
[cpp]
struct CNode
{
CNode() {}

inline bool operator<( const CNode& n ) const
{
return m_MaxDistance < n.m_MaxDistance ;
}
int Distance( const CNode& n ) const
{
return (int) (0.5 + EarthRadius * acos(
cos(m_Latitude ) * cos( n.m_Latitude ) * cos( m_Longitude - n.m_Longitude ) + sin( m_Latitude ) * sin( n.m_Latitude ) ) );
}
double m_Longitude ;
double m_Latitude ;

double m_MaxDistance ;
} ;

[/cpp]

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen » Wed Aug 13, 2003 12:30 pm

I think the following code is right, but I still get wrong answer.

It may be caused by precision.

Would you reveal the method you use to calculate the distance to me?

I need a more acurate method.

Thank you! :D

[cpp]
#include<stdio.h>
#include<math.h>

#define Max 1000

double Q(double);

int main(){
int n;
int i,j;
const double p=acos(-1)/180;
double s[Max][2];
double r[Max][3];
double dis[Max];
double psi,theda;
int ans;
double max,temp;
while(scanf("%d",&n)!=-1){
for(i=0;i<n;i++){
scanf("%lf%lf",&s[0],&s[1]);
theda=p*s[1],psi=p*s[0];
r[2]=sin(psi);
r[0]=cos(psi)*cos(theda);
r[1]=cos(psi)*sin(theda);
}
for(i=0;i<n;i++){
max=0;
for(j=0;j<n;j++){
temp=Q(r[0]-r[j][0])+Q(r[1]-r[j][1])
+Q(r[2]-r[j][2]);
if(temp>max)
max=temp;
}
dis[i]=max;
}
ans=n-1;
for(i=n-2;i>=0;i--){
if(dis[i]<dis[ans])
ans=i;
}
printf("%.2lf %.2lf\n",s[ans][0],s[ans][1]);
}
return 0;
}

double Q(double input){
return input*input;
}

[/cpp]

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Wed Aug 20, 2003 7:57 am

I am not sure if your formula is correct, but precision is quite important in this question.

Try to change this part

Code: Select all

         for(i=n-2;i>=0;i--){
            if(dis[i]<dis[ans])
                ans=i;
        }
to

Code: Select all

         for(i=n-2;i>=0;i--){
            if(dis[i]<dis[ans] || fabs(dis[i] - dis[ans]) < 1e-6)
                ans=i;
        }
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen » Wed Aug 20, 2003 6:12 pm

Why by this step can improve the precision of the code?

Would you like to tell me more about this? :D

Aftering adding your suggestion, I still got WA.

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

10316 - WA

Post by Nazmul Quader Zinnuree » Wed Aug 31, 2005 3:23 pm

I'm getting WA...
Why???...
Here's my code

Code: Select all

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

#define MAX 1005

const double PI = 2.0 * acos(0.0);
const double R = 6378.0;

double lat[MAX], lon[MAX];

double distance(int i, int j)
{
	double p_lat, p_long, q_lat, q_long;

	p_lat = PI * lat[i] / 180;
	p_long = PI * lon[i] / 180;
	q_lat = PI * lat[j] / 180;
	q_long = PI * lon[j] / 180;

	return (acos( sin(p_lat) * sin(q_lat) + cos(p_lat) * cos(q_lat) * cos(p_long) * cos(q_long) + cos(p_lat) * cos(q_lat) * sin(p_long) * sin(q_long)) * R);
}

int main(void)
{
	int n, i, j, save;
	double sum, min;

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

		min = 1e20;
		for (i = 0; i < n; i++)
		{
			sum = 0;
			for (j = 0; j < n; j++)
				sum += distance(i, j);

			if (sum <= min)
			{
				min = sum;
				save = i;
			}
		}
		printf ("%0.2lf %0.2lf\n", lat[save], lon[save]);
	}
	return 0;
}

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:

10316 Airline Hub...

Post by arif_pasha » Tue Sep 13, 2005 9:18 am

can anyone tell me where am i making mistakes..
gettin wa all the time

::edit::
cutted after got accepted
....
Last edited by arif_pasha on Wed Sep 14, 2005 9:57 pm, edited 1 time in total.

Post Reply

Return to “Volume 103 (10300-10399)”