My approach for those problems is usually this one: build the simplest possible algorithm to solve it, which is usually a brute force naive approach, and then test/figure mathematically whether or not it's too slow. Most of the time it's good enough. When it's not you have a clear starting point to work on and optimize things around until the algorithm is efficient enough.
Here's a simple algorithm to solve Problem 3 on Project Euler (in C, but translating it to the Python should be trivial):
#include <stdio.h>
#include <math.h>
int isPrime(int n){
int i;
if (n==2)
return 1;
if (n%2==0)
return 0;
for (i=3;i<sqrt(n);i+=2)
if (n%i==0)
return 0;
return 1;
}
int main(){
long long int n = 600851475143;
int i = 3;
while (i<50000){
if (isPrime(i))
if (n%i==0)
printf("%d\n",i);
i+=2;
}
return 0;
}
Assuming that your square might be rotated against whatever coordinates system you have in place, you can't rely on there being any repetition of X and Y values in your four points.
What you can do is calculate the distances between each of the four points. If you find the following to be true, you have a square:
There are two points, say A and C which are distance x from each other, and two other points, say B and D which are also distance x from each other.
Each point {A, B, C, D} is an equal distance from the two points which aren't x away. i.e.: If A is x away from C, then it will be z away from both B and D.
Incidentally, the distance z will have to be SQRT((x^2)/2), but you don't need to confirm this. If conditions 1 and 2 are true then you have a square. NOTE: Some people are concerned about the inefficiency of square root. I didn't say that you should do this calculation, I just said that if you did you would get a predictable result!
The bare minimum of work that you would need to do would be to pick a point, say A and calculate the distance to each of the other three points. If you can find that A is x from one point and z from two other points, then you just need to check those two other points against each other. If they are also x from each other then you have a square. i.e.:
Since AB = AD, check BD:
Just to be sure, you need to check the other sides: BC and CD.
Since AC = BD and since AB = AD = BC = CD, this is therefore a square.
Along the way, if you find more than two distinct edge distances then the figure cannot be a square, so you can stop looking.
Working Example Implementation
I have created a working example on jsfiddle (see here). In my explanation of the algorithm, I use arbitrary points A, B, C, and D. Those arbitrary points happen to be in a certain order for the sake of walking through the example. The algorithm works even if the points are in a different order, however, the example doesn't necessarily work if those points are in a different order.
Thanks to: meshuai, Blrfl, MSalters and Bart van Ingen Schenau for useful comments to improve this answer.
Best Answer
A common way to do this is just to compare the coordinates of the mouse click with the coordinates of the square.
Suppose the square has top-left coordinate of x1, y1 and bottom-right is x2,y2.
A mouse click at mx, my is in the square if (mx>x1 and mx<x2 and my>y1 and my<y2).
If all the square are the same size and in a grid, you can give each square a number:
n = y * number of squares in a row + x.
Then to get n from a mouse click:
n = (width of grid in pixels / square width in pixels * number of squares in a row) + (height of grid in pixels / square height in pixels)