Obstacle Course

Problem code: COURSE

All submissions for this problem are available.

A number of traffic cones have been placed on a circular racetrack to form an obstacle course. You are asked to determine the largest sized car that can navigate the course. For simplicity, the cones are assumed to have zero width and the car is perfectly circular and infinitely maneuverable. The track itself is the area between 2 concentric circles.

Formally, the course can be navigated by a car of radius c if there exists a closed loop around the center of the track which lies between the circles forming the track, and every point on the loop is at least c distance away from each cone and each boundary of the track.

Input:

Input begins with an integer T (about 25), the number of test cases. Each test case begins with 2 integers r and R (1<=r<R<=25000). The racetrack is the area between the circles centered at (0,0) with radii r and R. The next line of input contains an integer N (0<=N<=500), the number of cones. N lines follow, each containing the coordinates of a cone. The coordinates are integers, and are guaranteed to lie within the track, and be distinct. Cases are separated by a blank line.

Output:

For each input, output on a single line the diameter of the largest car that can navigate the course, rounded to 3 decimal places.

Sample input:

1

5 10
3
6 0
5 7
-2 -7

Sample output:

2.720

Explanation:

The image below shows the course corresponding to the sample input. The black circles represent the boundaries of the racetrack, the small dots the cones, and the filled red circle the car. Also shown is one possible path of the car through the course.

sample course
Author: pieguy
Tester: innocentboy
Editorial http://discuss.codechef.com/problems/COURSE
Date Added: 9-06-2010
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

bounce!!!

ritwick @ 13 Aug 2010 11:00 PM

bounce!!!

i m getting rite ans on my

akash_d_learner @ 21 Aug 2010 04:04 AM

i m getting rite ans on my comp for this prob but while submitting i m getting wrong ans. pls help me to figure whats wrongin my code..

 

#include <cstdio>
#include <math.h>
using namespace std;
int main()
{
int t,r,rr,n,*a,*b;
float d,l1,l2,ln,le=25000;
scanf("%d",&t);
for(int i=0;i<t;i++)
{
scanf("%d%d%d",&r,&rr,&n);
a=new int [n];
b=new int [n];
for(int j=0;j<n;j++)
{
scanf("%d%d",&a[j],&b[j]);
d=sqrt(a[j]*a[j]+b[j]*b[j]);
l1=d-r;
l2=rr-d;
if (l1>l2)
ln=l1;
else
ln=l2;
if(le>ln)
le=ln;
for(int k=0;k<j;k++)
{
l2=sqrt(((a[j]-a[k])*(a[j]-a[k]))+((b[j]-b[k])*(b[j]-b[k])));
if(le>l2)
le=l2;
}
}
printf("%5.3fn",le);
}
}

 

thanks in advance.

can anyone explain what we

mukulbudania @ 1 Sep 2010 10:33 PM

can anyone explain what we are supposed to find?? i am not even able to get the question?? Thanks in advance..

u need to find the diameter

jyotigupta2203 @ 18 Oct 2010 12:09 AM

u need to find the diameter of the largest car that can pass through the area between the concentric circles.

the point of the obstacles are given .so the diameter can vary from r circle boundary to point (on line x=y) or from point to R circle boundary ..

can anyone please explain me

tarun_kumar @ 23 Nov 2010 07:29 PM

can anyone please explain me the application of prim's algorithm in solving this problem.

i know prim's algorithm but not getting its application in one of the solutions.

Can we modify the way input

meher_almighty @ 2 Aug 2011 09:56 PM
Can we modify the way input is taken? or is it have to be in the exact same way given above?

hello friends.... the algo

abhipranay @ 14 Dec 2011 02:24 PM
hello friends.... the algo which i am following seems right to me to solve this problem but i am getting wrong answer on submission. for sample input my answer is correct.

hi @admin i do really think

konvimartial @ 20 Jun 2012 08:16 PM
hi @admin i do really think that there is an error with the test cases of this exercice,it sending me a wrong answer(more than ones) despite a have make an input file of my own where i think i really take the most extreme cases and it gives me correct answer can you guy actually verify the test cases please!!

can anyone help me out.. i am

madhavan @ 25 Aug 2012 01:04 AM
can anyone help me out.. i am new here.. I am getting correct answer for the sample input given above on my PC ,but when i submit it ..it gives me a runtime error msg.. Is there some problem with the program or what.. ? I have written this program in java..

the deed is done but what's

blueflamebisla @ 22 Sep 2012 01:28 AM
the deed is done but what's up with the java I/O of these guys. it's not taking the input the way it should.... bad management guys.. at least show us the WRONG output for debugging... DISAPPOINTED

@admin plz tell us the test

adlakhapiyush @ 22 Oct 2012 11:21 PM
@admin plz tell us the test case so that we cn figure out the problem bcoz its not giving write answer to most of us.

i am getng runtime error in

harsh93 @ 25 Nov 2012 10:39 PM
i am getng runtime error in it..plz can any1 explain y ?? #include #include int main() {float tem,d[4]={0},D[4]; int co[4][2],i,j,c,r,R,k ,t; scanf("%d",&t); while(t--) {scanf("%d%d%d",&R,&r,&c);for(i=0;i(d[k]-r)) {D[k]=(R-d[k]);} else{D[k]=(d[k]-r);}k++;} for(i=0;iD[j]){ tem=D[i]; D[i]=D[j]; D[j]=tem;}}}printf("%fn",D[c-1]);}return 0;}

@author pieguy pls give me 1

vish4071 @ 31 Dec 2012 06:16 PM
@author pieguy pls give me 1 or 2 test cases for which my code is wrong... id: 1657175

Hello All, this question has

manmohanvyas @ 14 Jan 2013 10:21 PM
Hello All, this question has problem with inputs , it can be proved by Making two programs in java, one taking input by Scanner other by BufferedReader. one with buffered reader will always give you RUNTIME ERROR(non-zero exit code).

Hey All, I am getting "Wrong

paradigmwit @ 14 Feb 2013 05:24 PM
Hey All, I am getting "Wrong Answer" for my solution. Any pointers to what i am doing wrong will be appreciated. My code is at here - http://www.codechef.com/viewsolution/1839873

this is my code and i m

doggysaurabh @ 23 Feb 2013 05:30 PM
this is my code and i m getting runtime error import java.util.*; public class obstrk{ public static double sqr(int a){ return a*a; } public static double modulus(int a, int b){ return Math.sqrt(sqr(a)+sqr(b)); } public static double max(double n1, double n2 ){ if (n1

@doggysaurabh : You need to

vineetpaliwal @ 23 Feb 2013 05:41 PM
@doggysaurabh : You need to name the file as Main.java and the class as Main in which the public static void main(... method should reside . Otherwise codechef judge will throw , "No Main class found" exception and hence a runtime error .

SUCCESSFUL SUBMISSIONS


Fetching successful submissions

HELP




 





Program should read from standard input and write to standard output.  After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:


 


    
    
  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.

    • 
    
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.

    • 
    
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.

    • 
    
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.

    • 
    
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • 
    If you are still having problems, see a sample solution here.