11243 - Texas Trip
Posted: Sun Jul 15, 2007 3:06 pm
can someone please give a hint on this problem?
Thank you
Thank you
can any one tell me his algorithm
i'm so confused
Page 1 of 2
Posted: Sun Jul 15, 2007 7:40 pm
hi;
can any one tell me his algorithm
i'm so confused
can any one tell me his algorithm
i'm so confused
Posted: 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.
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.
Posted: 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.
Posted: 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.
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.
Posted: 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...
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...
Posted: 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.
Posted: Tue Jul 17, 2007 8:15 am
I mean 0<=t<90, that was my mistake.
Posted: 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;
}
Posted: Thu Jul 19, 2007 3:30 am
andysoft: your program doesn't use any ternary search, so your solution might not be accurate enough.
Posted: 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:
But what is the function "f" in our task? I cannot understand.
Thanx in advance.
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
Thanx in advance.
Posted: 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"
In this problem, f(x) means "the area of the smallest square containing all of the points"
Posted: 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.
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.
Re: 11243 - Texas Trip
Posted: 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
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
Re: 11243 - Texas Trip
Posted: 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.