11243 - Texas Trip

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

11243 - Texas Trip

Post by fpavetic » Sun Jul 15, 2007 3:06 pm

can someone please give a hint on this problem?

Thank you

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv » Sun Jul 15, 2007 7:40 pm

hi;
can any one tell me his algorithm

i'm so confused :(

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Jul 15, 2007 10:13 pm

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.
Last edited by sclo on Tue Jul 17, 2007 8:15 am, edited 3 times in total.

klopyrev
New poster
Posts: 8
Joined: Tue Dec 26, 2006 10:37 am

Post by klopyrev » Sun Jul 15, 2007 11:32 pm

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Jul 15, 2007 11:36 pm

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
New poster
Posts: 9
Joined: Sat Jul 07, 2007 5:47 pm
Location: Denmark

Post by David Kjaer » Tue Jul 17, 2007 5:11 am

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... :)
Randers FC l

klopyrev
New poster
Posts: 8
Joined: Tue Dec 26, 2006 10:37 am

Post by klopyrev » Tue Jul 17, 2007 7:48 am

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Jul 17, 2007 8:15 am

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

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Wed Jul 18, 2007 4:40 pm

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;
}
Now I lay me down to sleep...
my profile

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Thu Jul 19, 2007 3:30 am

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

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Thu Jul 19, 2007 10:35 am

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.
Now I lay me down to sleep...
my profile

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

Post by Wei-Ming Chen » Thu Jul 19, 2007 12:21 pm

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Jul 20, 2007 6:14 am

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
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 11243 - Texas Trip

Post by sith » Mon Sep 10, 2012 3:29 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11243 - Texas Trip

Post by brianfry713 » Mon Sep 10, 2012 10:18 pm

To cover the holes with an area of 40 you'd have to use a rectangle not a square.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 112 (11200-11299)”