Enumerate Nondegenerate Triangles
Autumn Tournament (2011)
Submission name: triangles.cpp
Problem summary
Given named planar points, print every triple that forms a nondegenerate triangle. Preserve input order both inside each triple and between triples.
Input
N, then N rows containing an uppercase point name and integer coordinates.
Output
Valid triples, one per line with names separated by spaces; if none exist, print No triangles.
Constraints
3 ≤ N ≤ 26; −2000 < x,y < 2000.
Worked example
Original statement sample.
Input
5 A 0 0 B 5 0 C 0 4 D 10 0 E 0 8
Output
A B C A B E A C D A D E B C D B C E B D E C D E
Solution analysis
- Three points form a triangle exactly when they are not collinear. For points A,B,C, the cross product (Bx−Ax)(Cy−Ay)−(By−Ay)(Cx−Ax) is twice their signed area. Test whether it is nonzero; no division or floating-point arithmetic is necessary.
- Enumerate index triples i<j<k using three nested loops. This naturally emits triples in their required input-index order and never repeats one. Point names are labels, not sorting keys.
- In the sample A,B,D lie on the horizontal axis, so A B D is omitted. A,C,E are also collinear and omitted. The other eight triples have nonzero area and are printed.
Why it works
Each set of three distinct input positions has one unique ordered index triple i<j<k. Its determinant is nonzero exactly when the three points are noncollinear. Therefore the loops print precisely every valid triangle once and in the requested order.
Watch out. Do not sort point labels alphabetically. A zero-area triple is not a triangle. Use long long for cross-product arithmetic so coordinate products remain safe if bounds are extended. Print the exact no-result punctuation.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
struct Point{
char name;
long long x;
long long y;
};
int main(){
int n;
cin>>n;
vector<Point>points(n);
for(Point&point:points){
cin>>point.name>>point.x>>point.y;
}
bool found=false;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
for(int k=j+1;k<n;k++){
// A nonzero determinant means a nonzero triangle area.
long long area=(points[j].x-points[i].x)*(points[k].y-points[i].y)-
(points[j].y-points[i].y)*(points[k].x-points[i].x);
if(area!=0){
cout<<points[i].name<<' '<<points[j].name<<' '<<points[k].name<<'\n';
found=true;
}
}
}
}
if(!found){
cout<<"No triangles.\n";
}
}