10316  Airline Hub
Moderator: Board moderators
10316  Airline Hub
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).

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
No
Compare the problem statement of Waterloo contest and 50th contest. There is a slight difference
Re: No
Thanks. The problem was a roundoff error... I added an epsilon check and got AC.shahriar_manzoor wrote:Compare the problem statement of Waterloo contest and 50th contest. There is a slight difference
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.

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
Reply
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 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.
10316 Airline Hub
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.
I find that my O(n^2) algorithm is quite slow when compared to other people on ranklikst.

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
10316  Airline Hub  Please help
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:
Thank all for help or some test cases ...
Regards
Dominik
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;
}
Regards
Dominik

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

 New poster
 Posts: 16
 Joined: Fri Oct 11, 2002 11:03 pm
 Location: France
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]
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]
 Ghost77 dimen
 Learning poster
 Posts: 67
 Joined: Sun Sep 22, 2002 5:40 am
 Location: Taiwan
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!
[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=n1;
for(i=n2;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]
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!
[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=n1;
for(i=n2;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]
I am not sure if your formula is correct, but precision is quite important in this question.
Try to change this part
to
Try to change this part
Code: Select all
for(i=n2;i>=0;i){
if(dis[i]<dis[ans])
ans=i;
}
Code: Select all
for(i=n2;i>=0;i){
if(dis[i]<dis[ans]  fabs(dis[i]  dis[ans]) < 1e6)
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.
 Ghost77 dimen
 Learning poster
 Posts: 67
 Joined: Sun Sep 22, 2002 5:40 am
 Location: Taiwan

 New poster
 Posts: 42
 Joined: Sun Jul 31, 2005 2:07 am
 Location: SUST. Bangladesh
 Contact:
10316  WA
I'm getting WA...
Why???...
Here's my code
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;
}

 New poster
 Posts: 42
 Joined: Fri Jun 13, 2003 3:47 pm
 Location: Dhaka , Bangladesh
 Contact:
10316 Airline Hub...
can anyone tell me where am i making mistakes..
gettin wa all the time
::edit::
cutted after got accepted
....
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.