11378 - Bey Battle

[sonyckson]

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]

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]

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]

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]

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]

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]

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!

[jvimal]

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]

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]

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)

[metaphysis]

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';
    }
}