## 11378 - Bey Battle

Moderator: Board moderators

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

### 11378 - Bey Battle

Hello!, are there tricky cases in this problem?? ( as for in problem A ?? ).... I understand intersection of squares as intersection of their areas... is that right?....

My algorithm runs in O( n log(n)^2 ), and do a binary search in the square size. I have a function that tells me if for all squares of size K ( K even natural ) is there any intersection. Thanks! Eric.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

### Re: 11378 - Bey Battle

sonyckson wrote:Hello!, are there tricky cases in this problem?? ( as for in problem A ?? )
I don't think there is any tricky case.
I understand intersection of squares as intersection of their areas... is that right?....
Yes. Touching is OK.
My algorithm runs in O( n log(n)^2 ), and do a binary search in the square size. I have a function that tells me if for all squares of size K ( K even natural ) is there any intersection. Thanks! Eric.
Are you sure your function works?
This problem is a variety of Closest Pair Problem, so you could just modify the algorithm for Closest Pair Problem to solve this problem.
-----
Rio

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina
Well, my idea is the next:

Just when i get all the points, i sort them by their x value. then I do binary search to get the square size. My function has 2 sets one has pairs of points beggining with the x-value, and the other pairs of points begining with the y-value ( lets call them conjx and conjy ) , i iterate for every point (in the sorted by the x-value order) and in each iteration i do the next:

1- eliminate all the points of my conjx set which x-value differ from my actual point x-value by more or just K ( K = length of square in the function ).
2- i make the point P = (y-K+1, -1000001), where y is the y-value of my actual point ( of the actual iteration i mean ), then i find the lower point, greater than P, and if this point y-value has a difference with my actual y-value of less than K ... then that point and my actual point must have intersecting squares and the function finish.
(this because their x's and y's difference both differ in less than K )
3- I insert my actual point in the conjx and in the cony ( after swaping y and x ).

Here is the code...
( i used long long because i dont know which is the bug, but i know it is not neccesary )

Edited.

Thanks!. Eric.

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina
Actually, there was a tricky thing for me in the problem statement, i didnt realize that the square sides might not have integer coordinates. My approach is ok, and i also did the closest point idea, which showed to be easier to implement .Thanks! gl! Eric.

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm
sonyckson wrote:Actually, there was a tricky thing for me in the problem statement, i didnt realize that the square sides might not have integer coordinates. My approach is ok, and i also did the closest point idea, which showed to be easier to implement .Thanks! gl! Eric.
For this problem, would the approach:
"
Find the _points_ that correspond to the closest pair of points on the plane. And then, see what square can fit between these two points
"
work? I have a feeling that it would. Since there is no different orientation of the square possible.

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina
mmmm.. suppose you have points (0,0)....(0,4).... and (3,7).... the closest points are (0,0) and (0,4) ( if i am not so sleep ).... then your answer would be 4... but the correct answer is 3.

Suppose you have two points on the plane, how do you get the greatest size of the squares? When you get that you can see how to use the closest point algorithm. gl! , Eric.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
Well when i set this problem i was looking for an O(N) algorithm. But i could not find. After that i implemented an NlgN version which used BST which is quite hard to code. I completely overlooked modified closest pair solution. So i though it was going to be one of the hardest. But now i can see how easy it was! Hope you people liked it!
Self judging is the best judging!

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm
sonyckson wrote:mmmm.. suppose you have points (0,0)....(0,4).... and (3,7).... the closest points are (0,0) and (0,4) ( if i am not so sleep ).... then your answer would be 4... but the correct answer is 3.

Suppose you have two points on the plane, how do you get the greatest size of the squares? When you get that you can see how to use the closest point algorithm. gl! , Eric.
Hi,
When there are two points, redefine the dist between then as max(diffx/2, diffy/2). This is the size of the largest square.

This is the L-Inf metric. This can be transformed to L-1 metric by
(x,y)->(x-y, x+y).

but, I am unable to code this problem :'( Any hints on how to _code_ ? I got the theory part!

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina
jvimal wrote: When there are two points, redefine the dist between then as max(diffx/2, diffy/2). This is the size of the largest square.
Very near, the redefined distance ( the one should give us the size of the largest square ) betwen two points p1 = (x1,y1) and p2 = (x2,y2) is dist(p1,p2) = max(abs(x1-x2), abs(y1-y2) ).... now, use the closest point algorithm, think a little about the result. gl! Eric.

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 11378 - Bey Battle

It would've been nice if the lower value of N was defined. I don't think there were case with N == 1 (haven't tested though, I just printed 0 for that case)
hmm..

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 11378 - Bey Battle

Test data generator.

Code: Select all

``````#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, char *argv[])
{
srand(time(NULL));

cout << "100000\n";
for (int c = 1; c <= 100000; c++)
{
int n = rand() % 1000000;
if (rand() % 2 == 0)
cout << n;
else
cout << -n;
cout << ' ';
n = rand() % 1000000;
if (rand() % 2 == 0)
cout << n;
else
cout << -n;
cout << '\n';
}
}
``````