Four Matchsticks
National Olympiad — Municipal round (2016 season)
Submission name: matches.cpp
Problem summary
Use four unbroken matchsticks as the four sides of a rectangle. Determine whether this is possible. If so print its area; otherwise print the sum of the four lengths. A square is a rectangle.
Input
Four positive integer lengths.
Output
YES and the area on the next line if possible; otherwise NO and the total length on the next line.
Constraints
Each length is at most 1,000,000,000.
Worked example
An independently prepared example for this explanation.
Input
1 1 1 1
Output
YES 1
Solution analysis
- A rectangle has two pairs of equal opposite sides. After sorting the four lengths, this is equivalent to a[0] = a[1] and a[2] = a[3].
- When both equalities hold, the two different side positions have lengths a[0] and a[2], so their product is the area. Otherwise the requested total length is the sum of all four sticks.
- Four unit sticks satisfy both pairs and form a unit square with area 1. Lengths 1, 2, 3, 4 do not form equal pairs, so the output is NO and 10.
Why it works
Any rectangle must use equal opposite sides, so sorting its four lengths produces the two adjacent equal pairs. Conversely, two equal pairs can be placed opposite each other to form a rectangle. The condition is therefore necessary and sufficient, and the formulas then give exactly the requested area or total length.
Watch out. Use long long: area can be 10^18 and the sum can exceed signed 32-bit range. Squares are valid.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<long long> length(4);
for (long long &value : length) {
cin >> value;
}
sort(length.begin(), length.end());
// A rectangle needs two equal pairs of opposite sides.
if (length[0] == length[1] && length[2] == length[3]) {
cout << "YES\n" << length[0] * length[2] << '\n';
} else {
cout << "NO\n" << length[0] + length[1] + length[2] + length[3] << '\n';
}
return 0;
}