Seemingly an easy problem, I am looking for an algorithm to list every unique pair of points in a grid that are not collinear with the origin. The trick is to somehow avoid all the different symmetries and coincidences. This is what I have so far:

```
for( int x1 = 0; x1 <= s; x1++ ){
for( int y1 = 0; y1 <= s; y1++ ){
if( x1 == 0 && y1 == 0 ) continue; // P1 is coincident with origin
for( int x2 = x1; x2 <= s; x2++ ){
for( int y2 = 0; y2 <= s; y2++ ){
if( x1 == x2 && y2 >= y1 ) continue;
if( x1 * y2 == x2 * y1 ) continue; // points are collinear with origin
// this is a valid point
}
}
}
}
```

Enumerate all unique pairs (by defining an order on the grid points) and disregard those that are aligned with the origin.

```
def Pair(X0, Y0, X1, Y1):
if X0 * Y1 != X1 * Y0:
# Non collinear with the origin
Accept(X0, Y0, X1, Y1)
# Enumerate all (X0, Y0)
for X0 in range(NX):
for Y0 in range(NY):
# Enumerate all (X1, Y1) > (X0, Y0) in the lexicographical sense
# 1) X1 == X0, Y1 > Y0
X1= X0
for Y1 in range(Y0 + 1, NY):
Pair(X0, Y0, X1, Y1)
# 2) X1 > X0
for X1 in range(X0 + 1, NX):
for Y1 in range(NY):
Pair(X0, Y0, X1, Y1)
```

Or, better:

```
# Enumerate all (X0, Y0)
for X0 in range(NX):
for Y0 in range(NY):
# Enumerate all (X1, Y1) > (X0, Y0) in the lexicographical sense
for X1 in range(X0, NX):
for Y1 in range(0 if X1 > X0 else Y0 + 1, NY):
if X0 * Y1 != X1 * Y0:
# Non collinear with the origin
Accept(X0, Y0, X1, Y1)
```

Similar Questions

I have a list of objects that each have a specific attribute. That attribute is not unique, and I would like to end up with a list of the objects that is a subset of the entire list such that all of t

Given two lists of integers, generate the shortest list of pairs where every value in both lists is present. The first of each pair must be a value from the first list, and the second of each pair mus

I want to get every unique value in an ordinal scale (built from an array of an array). Let's say this is my dataset: var people = [ [Mary, Mary Smith, ID00001, 9.99 ], [James, James Smith,

I'm new to Lambda expressions so have been experimenting from an hour. I have a generic list - List<KeyValuePair<int, string>> basically holding a key and a value pair. I'm looking to pri

This is a general programming question although I would prefer a Node.js-geared solution. Are there any JavaScript or .NET APIs for retrieving a list of wireless access points and their associated dat

I want to get list of wifi access points.Thank you very much.My code is below public static void backupWifi(Context context) { WifiManager wifiManager = (WifiManager) context .getSystemService(Context

I've got a dataset with longitude/latitude points and an outcome value for each set of coordinates. I would like to create a spatial grid and then take the average of outcomes for coordinates that are

I have the following code: foreach (Tuple<Point, Point> pair in pointsCollection) { var points = new List<Point>() { pair.Value1, pair.Value2 }; } Within this foreach, I would like to be

I want to refresh the Kendo UI grid's contents every 60 seconds with up-to-the-minute data. EDIT: Here's how the dataSource is being assigned at initial configuration: parsedData = $.parseJSON(data);

I have a simple slideshow (jQuery Cycle) that displays an image every ten seconds (7 total images). In an adjacent div, I have a list with 7 bullet points. What's the easiest way to script a method in

I have a data set that has height values every so often, like topography data in a straight line with GPS coordinates. I used the GPS coordinates and trigonometry to make a cumulative distance column.

how to create grid lines in list view of windows form while designing

my question is how do create a unique id (which will go at the end of the URL, e.g. http://example.com/?id=12345) for every unique visitor who visits my site. I am also wondering how to track the visi

I'm looking for a motivational example for the closest pair of points problem http://en.wikipedia.org/wiki/Closest_pair_of_points_problem In itself it's a pretty self explanatory problem, but I can'

I am adding images to a grid in the code below. I need to be able to say, if molePopUp is being shown on the grid add one to an integer, so I can keep score of all the times the image is correctly pre

I can't seem to find a question on SO about my particular problem, so forgive me if this has been asked before! Anyway, I'm writing a script to loop through a set of URL's and give me a list of unique

I have a coding assignment and I need to free whatever memory I allocate, so I'm trying to delete all the semaphores that my unique_ptr's are pointing to. The unique_ptrs are all in a map. The code sn

I need a Pair list, with string, string. Tried : Dictionary<string, string> Categories= new Dictionary<string, string>(); but can't add 700, 2 and 700, 3. I need a Pair where

I'm new to using DateTime but I'm wondering if it is able to add every single day between two points to a list dynamically. For example, my code looks like this: { startTime = new DateTime(startYear,

I have a two dimensional function and I want to compute the elements of the function on the grid points but the two loops over rows and columns are very slow and I want to use multiprocessing to incre

i need to store non unique key value pair like in an application which can only be compiled with java 1.4. It should look like : {key1=>value1, key2=>value2, key3=>value3, key3

I've been using LINQ for a while now, but seem to be stuck on something with regards to Unique items, I have the folling list: List<Stock> stock = new List<Stock>(); This has the followin

I am having problems with making a method that will return distinct integers of the array list. I really want to do it with removing the duplicates and then just display the array list. I cannot figur

I was wondering how I would take a list, ex a = [1, 5, 2, 5, 1], and have it filter out unique values, so that it only returns a number that only occurred once in the list. So it would give me a=[2] a

I have a dataset of 900K randomly sampled coordinate points with a value associated with each point. I want to make a grid on the map and assign each cell the avg value of all the points that lie with

I have a list of points of interest in a plist file containing point info + longitude & lattitude. I wonder how to show in a MapView the nearest points to me according to a radius ? example : radi

I have a list of numbers, and I need to create every possible unique combination of the numbers in the list, without repeats, using a LINQ query. So, for example, if I have { 1, 2, 3 }, the combinatio

How to use grid view and list view in monodroid? give some example.

Managed to solve problem now I have a set of around 50 thousand points that have coordinates and one value associated with them. I would like to be able to place points into a grid averaging the asso

I have about 50K files is a directory (linux OS) and they have naming convention as USER_ID.ORACLE_JOB_ID.SEQUENCED_NUMBER.pdf I need to list all unique ORACLE_JOB_ID in a text file. How can this be d

I am writing a Cuda application that should calculate a function over two elements of my set S. But the order of the pair doesnt make any difference, so: f(a,b) = f(b,a) For that reason, I want to gen

How can we create unique object list in Swift language like NSSet & NSMutableSet in Objective-C.

I have two sets of strings that I need to match, if possible, by identical substrings in each pair (bold text in examples below; bold/capitalization only done here for emphasis there's not a way to id

I would like to return the count of the unique values for every column in a table. For example, if I have the table: Testdata <- data.frame(var_1 = c(a,a,a), var_2 = c(b,b,b), var_3 =

I have a class of type Dependency: class Dependency { public int Source; public int Target: } Given a list of List<Dependency> I would have the following list (each line is a Source/Target pair

I have a list of points in 2D space that form an (imperfect) grid: x x x x x x x x x x x x x x x x What's the best way to fit these to a rigid grid (i.e. create a two-dimendional array and work out w

In a rectangular grid of size m*n, the number of paths from (0,0) to (m,n) (without backtracking) is (m+n)!/(m!*n!). Now if there are certain points in the grid which we want to avoid, how can we calc

Input: list of 2d points (x,y) where x and y are integers. Distance: distance is defined as the Manhattan distance. ie: def dist(p1,p2) return abs(p1.x-p2.x) + abs(p1.y - p2.y) What is an efficient a

How i get max pair in a list of pairs with min y? I got this list: L =[[1,3],[2,5],[-4,0],[2,1],[0,9]] With max(L) i get [2,5], but i want [2,1].

I've got a list of audiobook parts that looks something like.. 20,000 Leagues Under The Sea A Tale of Two Cities Part 1 of 2 A Tale of Two Cities Part 2 of 2 A Canterbury Tale 1 A Canterbury Tale 2 Gr

Is it possible for the seperate users to see the unique changes they made to django admin? For example if user1 has added some products or categories to be able to see his unique changes - admin site?

My home work has been driving me up the wall. I am supposed to write a function called myRepl that takes a pair of values and a list and returns a new list such that each occurrence of the first value

I am trying to implement a simpler version of this algorithm but which works better than the quadratic algorithm. My idea basically is to sort the points by only x coordinate and try to solve it from

I have an isometric grid system who's coordinates start from [0,0] in the left hand corner of the grid (The corner shown in the above image) with x incrementing towards the bottom of the image and y i

I'm currently calculating the unique permutations of an array of data. While the following code is working, it's not as efficient as I would like. Once I get over 6 or 8 items, it becomes very slow an

I'm doing some algorithm practice and came across this. I have a list/array, something like this: [1, 5, 4, 9, 10, 2, ...] How would I go about returning finding unique sets of the list that have the

How can I check if a list in lisp is a dotted pair? CL-USER 20 : 3 > (dotted-pair-p (cons 1 2)) T CL-USER 20 : 3 > (dotted-pair-p '(1 2)) NIL CL-USER 20 : 3 > (dotted-pair-p '(1 2 3)) NIL I

You have an ascending list of numbers, what is the most efficient algorithm you can think of to get the ascending list of sums of every two numbers in that list. Duplicates in the resulting list are i

I want to build an android like main navigation that fits into a Susy Grid. It looks like this: The code goes here: HTML: <div class=container> <nav> <ul class=horizontal-list>

I have a very small database which includes 6 points, with those coloums id, the_geom, descr. And my aim to write a PL/pgSQL function which finds the the pair of points whose distance from each other