11243 - Texas Trip

[fpavetic]

can someone please give a hint on this problem?

Thank you

[hamedv]

hi;
can any one tell me his algorithm

i'm so confused

[sclo]

Ok, I'll give a hint on how I did it:

1. obviously the side of the minimum enclosing square must all lie outside or touch the convex hull.

2. at least 3 sides of the square will touch either a vertex of the convex hull or a side of convex hull.

3. Minimizing the area of the square is same as maximizing the length of the side of the square.

More hints:

4. for angles 0<=t<pi/2, define f(t) as the length of the side of minimum enclosing square with 2 sides in the direction of angle t from the x-axis.

5. Given t, to compute f(t) requires some linear algebra. Basically we want to rotate all the vertices of convex hull by angle -t and find the maximum and minimum x,y values, and return max(ymax-ymin,xmax-xmin)

6. Now, we need to compute the minimum f(t) over all 0<=t<pi/2.
Figure out how to do it efficiently.

7. Although I haven't proved it yet, the critical points of f(t) either corresponds to angles t in the directions of sides of convex hull, or the local minimas.

8. Use ternary search to find the minimum f(t) between each critical angles t1,t2.

PS: instead of angle t, we can also use vectors to parametrize the function f, leading to better accuracy.

[klopyrev]

I think you are making this problem too complicated. Convex Hull is not needed at all. I did it just using the concept of rotating all the points by an angle 0<=t<pi/2. That's 90*. With the points rotated, you can find the minx, maxx, miny, maxx and the smallest square will have the side max(maxx-minx, maxy-miny). No convex hull needed. And like it was said already, the minumum of this function f(t) is needed. To find the minimum of the function, you can use tertiary search, but you have to be careful, since there may be local minimums, as well as the absolute minumum. As for the details on how to take care of that, you have to figure it out. My solution is the fastest right now at 0.012 seconds, but I don't think it will hold for much longer.

[sclo]

convex hull is required for the proofs that my ternary search will in fact find the solution. I.e. the function is either concave up, or linear.

I believe that this method is called rotating caliper.

PS: my method is O(nlogn + nD) where D is the number of iterations that I use in the ternary search. I just use D=100.

It is also clear how to derive O(n^2*logn + n^2*D) solution from my solution that is much much easier.

[David Kjaer]

Why do you use 0<=t<=180.. Every polygon you get by rotating beyond 90 degrees is just a reflection of one you've already seen....

To klopyrev.. My approach is almost exactly the same as yours, and I got AC in 0.078, so you're record might stand for a while...

[klopyrev]

If only there weren't people like Loiane Groner, my solution would still be the fastest at 0.012. Anyone else want to get 0.000 seconds? The test input/output is on the Waterloo Programming Contest website.

[sclo]

I mean 0<=t<90, that was my mistake.

[andysoft]

and why do I get WA then?? I rotate points...

Code: Select all

#include <cstdio>
#include <math.h>
#include <iostream>
#include <cstdlib>

const
	double PI = 3.14159265358979323846;

using namespace std;
void f(double &x,double &y,double beta) {
double xt,yt;
  xt = x*cos(beta) - y*sin(beta);
  yt = x*sin(beta) + y*cos(beta);
  x = xt;
  y = yt;
}
double abs2 (double n) {
	return n<0?-n:n;
}
double max2(double a, double b) {
	return a>b?a:b;
}

int main(int argc, char* argv[]) {


 int ci,cn;
 int i,n;
  double x[51],y[51],x1[51],y1[51];
  double minx,maxx,miny,maxy,e1,ans,alpha;

	cin >> cn;

  for (ci=1;ci<=cn;ci++) {
	cin >> n;
	for (i=1;i<=n;i++)
		cin >> x[i] >> y[i];

	alpha = 0;
	for (i=1;i<=n;i++) {
		x1[i] = x[i];
		y1[i] = y[i];
	}

	ans = 20000000;
	while (alpha<=PI){
	for (i=1;i<=n;i++) {
		x[i] = x1[i];
		y[i] = y1[i];
	}
	  minx = 2000000;
	  maxx = -minx;
	  miny = minx;
	  maxy = -minx;

	  for (i=1;i<=n;i++) {
		f(x[i],y[i],alpha);
		if (x[i]<minx)
		  minx = x[i];
		if (x[i]>maxx)
		  maxx = x[i];
		if (y[i]<miny)
		  miny = y[i];
		if (y[i]>maxy)
		  maxy = y[i];
	  }

	  e1 = max2(abs2(minx-maxx),abs2(miny-maxy));
	  e1 = e1*e1;

	  if (e1<ans)
		ans = e1;

	  alpha = alpha + PI/2000.0;
	}
	printf("%.2f\n",ans+0.00001);
  }
	return 0;
}

[sclo]

andysoft: your program doesn't use any ternary search, so your solution might not be accurate enough.

[andysoft]

Well, I have read google and wiki about the Ternary Search, but please explain me the use of it in this task. In pseudo code this algo looks nearly this way:

Code: Select all

function ternarySearch(f, left, right, absolutePrecision) 
//left and right are the current bounds; the maximum is between them
    if (right-left < absolutePrecision) return (left+right)/2
    leftThird := (left*2+right)/3
    rightThird := (left+right*2)/3
    if (f(leftThird) < f(rightThird))
        return ternarySearch(f, leftThird, right, absolutePrecision)
    else
        return ternarySearch(f, left, rightThird, absolutePrecision)
end

But what is the function "f" in our task? I cannot understand.
Thanx in advance.

[Wei-Ming Chen]

I think f() is the value of the function you want to find the max/min

In this problem, f(x) means "the area of the smallest square containing all of the points"

[sclo]

Note that the code above finds the maximum, not the minimum.
Well, also to solve this problem, you need to figure out what the left and right values should be. That's because the ternary search will only find the minimum if there is only one local minimum between left and right.

[sith]

Hi

Can anybody explain correctness of problem sample input.

Why the square for this case is 242. I believe that it has to be 40. Where is my mistake?

4
10 1
10 -1
-10 1
-10 -1

[brianfry713]

To cover the holes with an area of 40 you'd have to use a rectangle not a square.