PLANT LOCATION

• Problem Description

  
  "A new highway called Highway 1 has just been built in the Kingdom of Byteland. Ingoo, the largest CPU manufacturer in Byteland, would like to build a new chipset plant along the highway.
  
  Ingoo currently has N warehouses in the kingdom. None of these warehouses are near the new highway. Chipsets manufactured from the new plant must be delivered to the warehouses. Thus, the further the distances from the new plant to the warehouses, the more the delivery cost Ingoo needs to bear.
  
  Therefore, the CEO of Ingoo would like to find a place on Highway 1 to build the new plant in such a way that the total distance from the plant to all the warehouses is minimized.
  
  You are visiting Byteland on December vacation and have decided to help Ingoo to locate the new plant!"

• CODING ARENA

• #include <stdio.h>

  #include<math.h>

  int x[2500],y[2500];

  int n;

  double a,b,c,d;

  #define EPS 0.000000001

  double udalj(double x,double y)

  {

    return sqrt(x*x+y*y);

  }

  double fja(double tt)

  {

    double ukupno=0;

    int i;

    for(i=0;i<n;i++)

      ukupno+=(a*(a*tt+b-x[i])+c*(c*tt+d-y[i]))/udalj(a*tt+b-x[i],c*tt+d-y[i]);

    return ukupno;

  }

  double fja2(double tt)

  {

    double ukupno=0;

    int i;

    for(i=0;i<n;i++)

      ukupno+=udalj(a*tt+b-x[i],c*tt+d-y[i]);

    return ukupno;

  }

  int main()

  {

    int t,i;

    int aa,bb,cc;

    double gornja,donja,srednja;

    scanf("%d",&t);

    while(t--)

    {

      scanf("%d",&n);

      scanf("%d %d %d",&aa,&bb,&cc);

      for(i=0;i<n;i++)

        scanf("%d %d",&x[i],&y[i]);

      a=bb;

      c=-aa;

      if(aa==0)

      {

        b=0;

        d=-(double)cc/bb;

      }

      else

      {

        d=0;

        b=-(double)cc/aa;

      }

      for(gornja=1;fja(gornja)<0;gornja*=2);

      for(donja=-1;fja(donja)>0;donja*=2);

      while(gornja-donja>=EPS)

      {

        srednja=(gornja+donja)/2;

        if(fja(srednja)>0)

          gornja=srednja;

        else

          donja=srednja;

      }

      printf("%.6lf\n",fja2(srednja));

    }

    return 0;

  }

      

• 
  

• Test Case 1

  
  Input (stdin)

  1
  
  5
  
  3 -5 -7 
  
  1 3
  
  -2 4
  
  4 -7
  
  7 6
  
  3 3
  
  

  Expected Output

  26.232349

• Test Case 2

  
  Input (stdin)

  1
  
  4
  
  2 -5 -4 
  
  1 2
  
  -2 3
  
  4 -7
  
  7 5
  
  3 3
  
  

  Expected Output

  21.556151