Count Lines through Lattice Points
Autumn Tournament (2007)
Submission name: lines.cpp
Problem summary
Count distinct infinite straight lines containing at least two points of the integer grid 0≤x≤a, 0≤y≤b. Different pairs on the same line count only once.
Input
Two integers a and b.
Output
The number of distinct lines.
Constraints
0<a,b<3000.
Worked example
Original statement sample.
Input
2 2
Output
20
Solution analysis
- Horizontal lines contribute b+1, and vertical lines contribute a+1. For every other line, choose its shortest integer step (dx,dy), whose components are coprime. Consider positive dx and positive dy first; reflection gives the same number of negative-slope lines.
- A line is counted by its unique first grid point in this direction. There are (a+1−dx)(b+1−dy) point pairs one primitive step apart. Subtract the (a+1−2dx)(b+1−2dy) pairs that also have a predecessor, treating a negative factor as zero. Only the first adjacent pair of each line remains.
- For a=b=2, horizontal and vertical lines contribute 6. Primitive directions (1,1), (1,2), and (2,1) contribute 5,1,1 positive-slope lines. Reflecting these 7 lines gives 14 slanted lines, so the total is 20.
Why it works
Every slanted grid line has exactly one primitive direction up to sign and exactly one first adjacent pair in the chosen direction. The subtraction removes precisely pairs that are not first. Coprimality prevents counting a line again with a longer step, and reflection accounts for the opposite slope.
Watch out. Do not count every pair: collinear triples create duplicates. Use primitive directions, include horizontal/vertical lines, and clamp each predecessor factor to zero before multiplying.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<numeric>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
long long answer=a+b+2;
for(int dx=1;dx<=a;dx++){
for(int dy=1;dy<=b;dy++){
if(gcd(dx,dy)!=1){
continue;
}
long long pairs=1LL*(a+1-dx)*(b+1-dy);
long long nonfirst=1LL*max(0,a+1-2*dx)*max(0,b+1-2*dy);
// Keep the first adjacent pair on each line, then reflect its slope.
answer+=2*(pairs-nonfirst);
}
}
cout<<answer<<'\n';
}