8
\$\begingroup\$

Input

An integer n and a pair of distinct integer valued (x, y) coordinates on the boundary of the grid. The coordinates are indexed from 1. For example, n=10 and (1,2), (10, 7).

The points will always be on different sides of the grid and neither of them will be \$(1, 1)\$.

Output

The number of integer points in an n by n grid that are on the same side of the line as the coordinate (1,1). Points that are exactly on the line should be counted as well.

Examples

For n=10 and (1,2), (10, 7),

enter image description here

The output should be 41.

For n=8 and (8, 3), (3, 8),

enter image description here

The output should be 49.

For n=8 and (7, 1), (8, 2),

enter image description here

The output should be 63.

For n=8 and (1, 2), (2, 1),

enter image description here

The output should be 3.

\$\endgroup\$
15
  • \$\begingroup\$ Indicing from 1 seems quite weird \$\endgroup\$
    – l4m2
    Dec 25, 2023 at 11:24
  • 4
    \$\begingroup\$ @l4m2 Tell that to R coders :) \$\endgroup\$
    – Simd
    Dec 25, 2023 at 12:08
  • 3
    \$\begingroup\$ Having the axes cross at (1, n) seems even weirder. \$\endgroup\$
    – Neil
    Dec 25, 2023 at 14:43
  • \$\begingroup\$ @LuisMendo Example added. Thank you. \$\endgroup\$
    – Simd
    Dec 25, 2023 at 18:29
  • \$\begingroup\$ Is it acceptable if a point on the line is declared to be above or below because of floating-point numerical issues, producing a wrong answer? \$\endgroup\$
    – Luis Mendo
    Dec 25, 2023 at 18:55

6 Answers 6

3
\$\begingroup\$

APL+WIN, 32 40 bytes

Plus 8 bytes to comply with the question as it is now written. Works for all four examples given.

Prompts for x coordinates followed by y coordinates and then grid size

+/,0≤(↑n)×n←×n∘.-⌊(⊃1,¨n←⍳⎕)+.×⎕⌹⎕∘.*0 1

Try it online! Thanks to Dyalog Classic

\$\endgroup\$
0
2
\$\begingroup\$

JavaScript (Node.js), 99 bytes

(n,a,b,c,d,g=(x,y)=>(~y+b)*(c-a)-(~x+a)*(d-b))=>[...Array(s=i=n*n)].map(_=>s-=g(--i%n,i/n)*g()<0)|s

Try it online!

1-index

\$\endgroup\$
1
  • \$\begingroup\$ There was a bug in the question. Apologies. It is fixed now. \$\endgroup\$
    – Simd
    Dec 25, 2023 at 18:26
2
\$\begingroup\$

Charcoal, 35 bytes

≔…·¹NθNηNζ≔×⁻θζ⁻NηεIΣ⭆×⁻θη⁻Nζ⭆嬋ιλ

Try it online! Link is to verbose version of code. Takes five inputs starting with n. Explanation:

≔…·¹Nθ

Create a range from 1 to n.

NηNζ

Input the first point.

≔×⁻θζ⁻Nηε

Input the x-coordinate of the second point and subtract the x-coordinate of the first point from it, then for each integer from 1 to n multiply that by the y-coordinate subtracted from that integer.

IΣ⭆×⁻θη⁻Nζ⭆嬋ιλ

Input the y-coordinate of the second point and subtract the y-coordinate of the first point from it, then for each integer from 1 to n multiply that by the x-coordinate subtracted from that integer. Pair the elements of this array with those of the previous array and count the number of parings where the element of this array does not exceed the element of the previous array.

Note: The output depends on the input points being entered in the correct order. The inputs for the other test cases are as follows:

  • 8 3 8 8 3
  • 8 8 2 7 1
  • 8 1 2 2 1
\$\endgroup\$
2
\$\begingroup\$

Python 3.8, 109 bytes

lambda n,x,y,X,Y:sum(((a:=(Y-y)/(d:=x*Y-X*y))*-~(K%n)+(b:=(x-X)/d)*-~(K//n)-1)*(a+b-1)>=0for K in range(n*n))

Try it online!

(Even) Econ majors will know that a line can be described by the equation \$ax+by=1\$. So this solution just computes \$ax+by\$ for each point on the grid and compares it to \$1\$.

\$\endgroup\$
1
\$\begingroup\$

Jelly, 15 bytes

_þḢU×_/}Z>þ/¬SS

Try it online!

A dyadic link taking \$n\$ as the left argument and the points as the right argument as a list of two lists of integers.

This is loosely a Jelly translation of @Neil’s Charcoal answer so please upvote that one too!

Explanation

_þ              | Outer using subtract (will implicitly turn n into 1..n)
  Ḣ             | Head
   U            | Reverse order of innermost lists
    ×_/}        | Multiply by the difference between the two points
        Z       | Transpose
         >þ/    | Outer using greater than
            ¬   | Not
             SS | Sum and then sum again
\$\endgroup\$
1
\$\begingroup\$

Haskell, 86 bytes

n#(a,b,c,d)|(%)<-(\x y->(c-a)*(y-b)-(d-b)*(x-a))=sum[1|i<-[1..n],j<-[1..n],i%j*1%1>=0]

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.