11378  Bey Battle
Moderator: Board moderators
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.
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.
Re: 11378  Bey Battle
I don't think there is any tricky case.sonyckson wrote:Hello!, are there tricky cases in this problem?? ( as for in problem A ?? )
Yes. Touching is OK.I understand intersection of squares as intersection of their areas... is that right?....
Are you sure your function works?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.
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
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 xvalue, and the other pairs of points begining with the yvalue ( lets call them conjx and conjy ) , i iterate for every point (in the sorted by the xvalue order) and in each iteration i do the next:
1 eliminate all the points of my conjx set which xvalue differ from my actual point xvalue by more or just K ( K = length of square in the function ).
2 i make the point P = (yK+1, 1000001), where y is the yvalue of my actual point ( of the actual iteration i mean ), then i find the lower point, greater than P, and if this point yvalue has a difference with my actual yvalue 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.
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 xvalue, and the other pairs of points begining with the yvalue ( lets call them conjx and conjy ) , i iterate for every point (in the sorted by the xvalue order) and in each iteration i do the next:
1 eliminate all the points of my conjx set which xvalue differ from my actual point xvalue by more or just K ( K = length of square in the function ).
2 i make the point P = (yK+1, 1000001), where y is the yvalue of my actual point ( of the actual iteration i mean ), then i find the lower point, greater than P, and if this point yvalue has a difference with my actual yvalue 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.
For this problem, would the approach: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.
"
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.
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.
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.
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!
Hi,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.
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 LInf metric. This can be transformed to L1 metric by
(x,y)>(xy, x+y).
but, I am unable to code this problem :'( Any hints on how to _code_ ? I got the theory part!
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(x1x2), abs(y1y2) ).... now, use the closest point algorithm, think a little about the result. gl! Eric.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.
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..

 Experienced poster
 Posts: 117
 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';
}
}
My solutions for UVa problems: https://github.com/metaphysis/Code.