CHEFBR12 Editorial

editorial
,
1

Practice
Contest

Author: Maaz Bin Asad
Tester: Prasoon Jain
Editorialist: Maaz Bin Asad

DIFFICULTY

Easy-Medium

PREREQUISITES

Geometry

PROBLEM:

Chef is standing at some point whose coordinates are given to us. He needs to reach a given line of boxes in minimum time whose 2 or more random coordinates are given. Determine minimum time to reach there if he runs with a constant speed of 1 unit.
Given:

  1. Line is infinite
  2. Chef and boxes are point masses.

Quick Explanation:

We just need to find perpendicular distance of the point from given line.

Explanation:

Since, we are given at least two points, we can assume a third point which is the locus. We can equate slope of one given point with other given point using this locus.
For instance, we are given (x1,y1) and (x2,y2), then we can assume third point on the line (x,y) and equate their slopes : (x1-x)/(y1-y)=(x2-x)/(y2-y).
This will give us the equation of line of boxes.
After this, we can apply the formula for perpendicular distance of a point from a line.

TIME COMPLEXITY:

O(1) per test case.

SOLUTIONS:

Setter’s Solution:

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
ll t;
cin>>t;
while(t--){
    ll n;
    double a,b,x,y;
    cin>>n>>a>>b;
    vector<pair<double,double>>v;
    ll nn=n;
    while(nn--){
        cin>>x>>y;
        v.push_back({x,y});
    }
    double x1=v[0].first;
    double y1=v[0].second;
    double y2=v[1].second;
    double x2=v[1].first;
    double A=(y2-y1)/(x2-x1);
    double B=-1;
    double C=-(A*x1-y1);
    double ans=(A*a+B*b+C)/(double)sqrt(A*A+B*B);
    ans=abs(ans);
    ans=floor(ans);
    cout<<ans<<"\n";

 }
}

Tester’s Solution:

import java.util.Scanner;

 class GreatDepress {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
 int t=sc.nextInt();
 while(t>0) {
  
  int n=sc.nextInt();
  int a=sc.nextInt();
  int b=sc.nextInt();
  int x[]=new int[n];
  int y[]=new int[n];
  for(int i=0;i<n;i++) {
    x[i]=sc.nextInt();
    y[i]=sc.nextInt();
  }
  double A = (double)(y[1]-y[0]) / (double)(x[1]-x[0]);
  double B = -1;
  double C = -((long)A*x[0] - y[0]);
  double ans = (double)((long)A*a+(long)B*b+C)/(double)Math.sqrt((long)A*A+(long)B*B);
  
  ans=Math.abs(ans);
  int finalAns=(int) ans;
  System.out.println(finalAns);
  t--;
  }
  }
}