Segments
National Olympiad — Municipal round (2013 season)
Submission name: segments.cpp
Problem summary
Given a nondegenerate segment with integer endpoints, count all unordered nondegenerate segments perpendicular to it whose integer-coordinate endpoints satisfy 0<x<a and 0<y<b. Also count the distinct lengths among these segments.
Source clarification. The given object is a segment with a perpendicular direction, so its endpoints are understood to be distinct; the PDF does not separately spell out this nondegeneracy condition.
Input
x1 y1 x2 y2 a b.
Output
The total segment count and distinct-length count.
Constraints
All input integers are positive and less than 50.
Worked example
Official statement sample.
Input
1 1 2 2 4 4
Output
5 2
Solution analysis
- Let (dx,dy) be the given direction and g=gcd(|dx|,|dy|). Every integer perpendicular displacement is an integer multiple of the primitive vector (dy/g,−dx/g). Fix one sign of this vector to avoid counting a segment twice.
- Write u=|dy|/g and v=|dx|/g. A displacement of magnitude t times the primitive vector has (a−1−tu)(b−1−tv) placements, provided both factors are positive. Sum over positive t until one factor ceases to be positive.
- Each t gives a different positive length. In the sample u=v=1 and the interior grid is 3 by 3. The two possible steps contribute 2*2=4 and 1*1=1 segments, yielding 5 segments of 2 lengths.
Why it works
Integer solutions to dx·Δx+dy·Δy=0 are exactly multiples of the primitive perpendicular vector. Fixing a positive multiplier and one orientation represents each unordered segment once. The independent horizontal and vertical placement counts give the product, and distinct multipliers give distinct lengths.
Watch out. The grid boundaries are strict, so it has a−1 columns and b−1 rows. Horizontal and vertical input segments are valid.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<numeric>
#include<cstdlib>
using namespace std;
int main(){
int x1,y1,x2,y2,a,b;
cin>>x1>>y1>>x2>>y2>>a>>b;
int dx=abs(x2-x1);
int dy=abs(y2-y1);
int g=gcd(dx,dy);
// Absolute components of a primitive perpendicular lattice displacement.
int u=dy/g;
int v=dx/g;
long long total=0;
int lengths=0;
for(int t=1;a-1-t*u>0&&b-1-t*v>0;++t){
total+=(a-1-t*u)*(b-1-t*v);
++lengths;
}
cout<<total<<' '<<lengths<<'\n';
}