Thread: Urgent Help Needed!!! Plzz respond plzzz

  1. #1
    Registered User
    Join Date
    Aug 2013
    Posts
    3

    Urgent Help Needed!!! Plzz respond plzzz

    I have been given this task by my boss and i cant do it....pls help anyone plzzz... i have to make a program on the following task by today!!



    Consider a map that has the following properties;
    - the map is two dimensional
    - the map is perfectly square with dimensions 10000000x10000000
    - the map has an associated set of many features
    - the map does not "wrap around"

    Each feature on the map is described by a 2D coordinate in the range (0, 0) to (10000000, 10000000).

    Find the most isolated feature on the map, where the "most isolated feature" is the feature that is
    furthest (largest Euclidean distance) from any other feature. Because the map does not "wrap around", this should be a
    direct distance across the map.

    <----10000000---->
    --------------- -
    | A | |
    | | |
    | | 10000000
    | | |
    | B C | |
    | E D | |
    --------------- -

    In the example above, A is the most isolated feature on the square map with edge length 10000000.

    Write a program that reads in many features from standard input, and outputs the name of the most isolated
    feature to standard output. The format of the input is the feature name, x coordinate and y coordinate separated by spaces.
    Each feature is on a new line. There may be any number of features between 1 and 100000. The program should be fast, so the algorithm
    must be better than O(n^2).

    Any of the following languages are fine - C++, Python (>=2.5), C#, Java. The program shouldn't require any third-party libraries other
    than the chosen language's standard libraries, and should be compilable and runnable on a modern Windows or Linux development environment
    of your choice (e.g. MS Visual Studio, gcc, Eclipse etc). You should submit your program source code and any necessary makefiles or
    project files required for compilation. If you write the code in C++, using C++11 features is fine.


    Two example inputs are provided; problem_small.txt should output place6 and problem_big.txt should output place55163

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    I've got a better idea, let's play "spot the cross-posting frenzy"
    Urgent Help Needed!!! Plzz respond plzzz - C++ Forum

    Here's an idea - work on the problem, rather than wasting time finding forums to sign up to, most of which will tell you (in more or less similar terms to go fly a kite).

    > I have been given this task by my boss and i cant do it
    Perhaps your boss suspects that you know nothing at all.

    I think most of us here are just happy enough just to watch you fail, so your soon to be ex-boss can go about his business of finding someone COMPETENT to do the work.

    As opposed to someone like you who thinks they can cheat and scam their way through life by begging other people to keep your ass out of the fire.

    Just what is your plan here - assuming you manage to "pass" this test?
    One thing is for sure, you won't be able to do the next assignment any better than you did this assignment. You're going to rapidly run out of people willing to work for $0 while you sit on your ass collecting a paycheck.

    > i have to make a program on the following task by today!!
    I'm also curious as to why "boss" would accept an answer in a range of languages on a Sunday.
    Somehow, it smells more like homework left far too late for anyone to do anything reasonable with.

    In the meantime, here is some soothing music while you wait.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Mar 2010
    Posts
    583
    Definitely looks like homework. If it is, I'm amused that you think you'd have better luck asking people to do your job for you. That's not part of my definition of "help". Do some work and come back if you have a specific question.

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    This isn't really an programming issue as it is figuring out an algorithm. I wonder how many here could determine the optimal algorithm for doing this. It's not trivial. As mentioned though, since this appears to be homework, your supposed to show some work you've done in an attempt to figure out an algorithm before you'll get much help here.

  5. #5
    Registered User
    Join Date
    Jan 2011
    Posts
    222
    I don't think this is a homework question. It looks more like a job interview task that employers (at least where i come from) give you on Saturday evening expecting you to post a solution by Sunday 23:59 to see how bright and motivated you are and if you are willing to work on Sundays/Holidays. i had a similar task but since i was allowed to work in Perl (my MT ) the challenge was just to solve the problem. And from the looks of it, this is a quite interesting problem. Needless to say i quit the job after few months. no free Saturdays or Sundays killed me. So if this is something like that, think twice, because afterwords things get a lot more complicated and more demanding ...

    Also just by glancing through the problem i would suggest looking into RMQ problem solutions which can be used to get you to O(1) runtime (of course after O(n) or O(n^2) preprocessing time - it depends, but you'll figure it out)

    Cheers

    baxy

  6. #6
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    There are known O(n log n) algorithms for calculating all nearest neighbours (see Nearest neighbor search article in Wikipedia). One solution to the current problem is simply finding the maximum of these (and this search is obviously just O(n)), thus yielding an O(n log n) algorithm overall.

    The algorithms and techniques useful for this type of problem are closely related to Voronoi diagrams (Wikipedia), which is a dual to the Delaunay triangulation usually better known to programmers.

    In particular, I do believe a variant of Fortune's Algorithm (Wikipedia) would do here very nicely. Updating the minimum neighbour distance for each point at an event that changes the beach line (or indirectly, the Voronoi boundary), and keeping the maximum of those, should yield a nice implementation. (Note that slight imprecision in the location of the Voronoi boundaries should not affect the results, as long as the implementation finds all correct Voronoi boundaries.)

    Baxy, I do believe the current known minimum for this problem is O(n log n) (same as Voronoi diagrams and Delaunay triangulation). Since the queried element is the distance, calculating all distances would need O(n2) preprocessing; if the queried element is the minimum distance, then the elements need at least O(n log n) preprocessing (the output of all nearest neighbours algorithm). Thus, I don't think RMQ will help here.

  7. #7
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    What about a quadtree? The feature in the biggest box is the most isolated, gg wp.

    Edit: My bad, that would fail. Delaunay triangulation is how I would do it.
    Last edited by MutantJohn; 08-25-2013 at 05:37 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Urgent help needed
    By bathulasubbu in forum C Programming
    Replies: 3
    Last Post: 03-25-2011, 09:33 AM
  2. synchronous i/o URGENT HELP PLZZZ
    By doia in forum C Programming
    Replies: 3
    Last Post: 04-19-2010, 06:22 PM
  3. Urgent, help needed.
    By sinnclaus in forum C Programming
    Replies: 4
    Last Post: 03-29-2010, 06:08 AM
  4. beginner plzz help urgent
    By sara101 in forum C Programming
    Replies: 11
    Last Post: 01-14-2007, 10:38 PM
  5. Urgent help needed!!!
    By gibs21 in forum C Programming
    Replies: 2
    Last Post: 09-26-2002, 01:45 PM