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

Discussion of Problem 1726. Visits

AC in 0.09 ... a hint
Posted by Христо Попов (B&W) 23 Nov 2022 23:21
After some failed attempts with O(n)=n*n/2, finally I found an O(n)=n solution.
In plain C, it took 0.09s and 1.5Mb. (just from curiosity tried the same with C# - 14MB used RAM :))

The arrays of X and Y coordinates can be sorted independently from each other.

So basically, this input:
3
1 3
2 1
3 2
will have exactly the same result (which is 2) as
3
1 1
2 2
3 3
Re: AC in 0.09 ... a hint
Posted by Mr_Ell 16 Feb 2023 12:53
can you proof it?
Re: AC in 0.09 ... a hint
Posted by Losingways 9 Apr 2023 18:52
Assuming a (x1, y1), b (x2, y2), then the distance from c (x3, y3) to (x1, y1) and (x2, y2) is equivalent to the distance from (x1, y2) and (x2, y1)