All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Four Points in a Square (Posted on 2023-01-12) Difficulty: 4 of 5
Four points are chosen at random inside a square. Each point is chosen by choosing a random x-coordinate and a random y-coordinate.

A convex quadrilateral is drawn with the the four random points as the vertices.

Determine the probability that the center of the square is inside this quadrilateral.

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts preliminary simulation results | Comment 1 of 10
clearvars,clc
tic
hit=0; convCt=0;
for trial=1:2000000
  for i=1:4
    x(i)=2*rand-1; y(i)=2*rand-1;
    angle(i)=atan2d(y(i),x(i));
    if angle(i)<0 angle(i)=angle(i)+360;
    end
  end

  if isConvex(x,y)
    convCt=convCt+1;
    [angle,ix]=sort(angle);
    adiff=angle(2:4)-angle(1:3);
    adiff(4)=angle(1)-angle(4)+360;
    if max(adiff)<180
      hit=hit+1;
    end
  end
end
disp([hit convCt  hit/convCt])
toc

function conv=isConvex(x0,y0)
  for pt=1:4
     x=x0;y=y0;
     x(pt)=[]; y(pt)=[];
     x=x-x0(pt); y=y-y0(pt);
     conv=true;
     for i=1:3
       angle(i)=atan2d(y(i),x(i));
       if angle(i)<0 angle(i)=angle(i)+360;
       end
     end
     angle=sort(angle);
     if hasReflex(angle)==false
       conv=false;
       break
     end
  end
end


function t=hasReflex(angle) % requires angle be sorted
  adiff=angle(2:3)-angle(1:2);
  adiff(3)=angle(1)-angle(3)+360;
  if max(adiff)>180
    t=true;
  else
    t=false;
  end
end

The program tests for convexity by finding, for each point, the coordinates of the other points and computing their relative angles. Those angles are sorted, and each must include a reflex angle as the outermost angle, to be considered convex.

The results:

 721783         1388507         0.519826691547108
Elapsed time is 60.899897 seconds.

so it was able to do 2 million trials in one minute, of which 1,388,507 were convex, and among those 721,783 included the center of the square (found by a similar method of angles relative to the center). This gave a probability of 52.0% (fairly safe choice of precision).



  Posted by Charlie on 2023-01-12 09:49:53
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (3)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information