cppAcademy
FROM LEARNING TO COMPETING

Expert.
Put your skills to the test.

Bulgarian Informatics Group A · 2009–2026

217 independently explained problems: 54 Municipal, 54 Regional and 109 National. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group A also includes challenging national-level problems. The 109 National-round tasks shared by Groups A and B retain their existing permanent URLs and explanations. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP A2020 · MediumLattice geometry

Lattice Points on Segments

National Olympiad — Municipal round (2020 season)

Submission name: points.cpp

Solve in Editor →

Problem summary

Count distinct integer-coordinate points lying on at least one of the input segments, including endpoints. Duplicate and overlapping segments are allowed.

Input

n, then n lines x1 y1 x2 y2.

Output

The number of distinct covered lattice points.

Constraints

1 ≤ n < 5000; all endpoint coordinates are between −500 and 500; every segment has distinct endpoints.

Worked example

Official sample, transcribed with whitespace restored from the PDF.

Input

3
2 1 2 5
1 1 4 4
5 2 1 4

Output

10

Solution analysis

  1. For a segment displacement (dx,dy), let g=gcd(|dx|,|dy|). Its lattice points are exactly the start plus k·(dx/g,dy/g), for k=0,…,g. This includes horizontal and vertical segments without special cases.
  2. The coordinate bound makes a 1001 by 1001 boolean grid sufficient. Enumerate each segment’s lattice points and mark their shifted coordinates. Increase the answer only when a previously unmarked point is encountered, automatically handling overlaps and duplicates.
  3. The sample segments contain five, four, and three lattice points respectively. Two points are shared with already counted segments, so their union has 5+4+3−2=10 distinct points.

Why it works

The normalized displacement has coprime components, so it is the primitive lattice step along the supporting line. Every integer-coordinate point on the segment must occur at an integer multiple of this step, and the segment parameter bounds allow exactly k=0 through g. Thus enumeration visits all and only covered points. The boolean grid counts each visited coordinate once, giving the union size.

Complexity: O(1001²+Σ(g_i+1)) time and O(1001²) space; each g_i≤1000.

Watch out. Divide the signed displacements by a nonnegative gcd. Include both endpoints. Repeated points across segments contribute once.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: The normalized displacement has coprime components, so it is the primitive lattice step
// along the supporting line. Every integer-coordinate point on the segment must occur at an integer
// multiple of this step, and the segment parameter bounds allow exactly k=0 through g.
#include<iostream>
#include<vector>
#include<numeric>
#include<cstdlib>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int width=1001;
    vector<unsigned char>seen(width*width,0);
    int n,answer=0;
    cin>>n;
    while(n--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        int dx=x2-x1,dy=y2-y1;
        int steps=gcd(abs(dx),abs(dy));
        dx/=steps;
        dy/=steps;
        for(int k=0;k<=steps;++k){
            int x=x1+k*dx+500;
            int y=y1+k*dy+500;
            int index=x*width+y;
            if(!seen[index]){
                seen[index]=1;
                ++answer;
            }
        }
    }
    cout<<answer<<'\n';
}

Source: Arena Olimpiici ↗