ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1052. Rabbit Hunt

O(n^3) accepted fairly easy
Posted by Tabledott 13 Jun 2006 12:35
I coded O(n^3) that was accepted fairly easy... But I know there is O(n^2) algo but I don't know how to implement it.. Any Ideas?
Re: O(n^3) accepted fairly easy
Posted by Madhav 15 Jun 2008 15:04
Yaa i have the idea of O(n^2).First you can can calculate
the slopes of all lines in O(n^2).Create a class which contains the 2 points and the slope of the line joining two points.Note that there will be n(n+1)/2 nodes and define operator == as: slopes are equal and one point must be common to both the lines.
Re: O(n^3) accepted fairly easy
Posted by majorro 13 Oct 2020 05:00
I have tl with long double and wa with double on that O(n^2) solution

Edited by author 13.10.2020 05:01