Nested Triangles
National Olympiad — Regional round (2009 season)
Submission name: triangles.cpp
Problem summary
Find the longest chain of triangles such that each triangle lies entirely strictly inside the next. Vertices may coincide or lie on other triangle boundaries, but these contacts do not count as strict nesting.
Input
N followed by N lines, each with the three integer vertex coordinate pairs of a triangle.
Output
The maximum number of triangles in a strictly nested chain.
Constraints
1 ≤ N ≤ 1000; coordinates are between −1000000 and 1000000.
Worked example
An independently prepared example for this explanation.
Input
3 -1 -1 0 1 1 0 -5 -5 0 5 5 0 -10 -10 10 0 0 10
Output
3
Solution analysis
- Use signed cross products to test a point against the three oriented sides. A point is strictly inside a triangle exactly when all three products have the same nonzero sign. Convexity means that a triangle lies strictly inside another exactly when all three of its vertices pass this test.
- Sort triangles by absolute doubled area. Strict containment increases area, so this is a topological order. For each triangle j, start dp[j]=1 and extend every earlier triangle i contained in j.
- All three triangles in the example form one chain: the smallest lies strictly inside the middle, which lies strictly inside the largest. The dynamic program assigns lengths 1,2,3.
Why it works
The strict half-plane test characterizes the interior of a convex triangle. An inner triangle is the convex hull of its vertices, so testing all three vertices is sufficient and necessary. Each chain ending at j either contains only j or extends a chain ending at a smaller-area contained triangle. The recurrence examines exactly these possibilities in valid order.
Watch out. A zero cross product means boundary contact and must be rejected. Use signed 64-bit arithmetic for coordinate differences and cross products.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cstdlib>
#include<iostream>
#include<vector>
using namespace std;
struct Point{
long long x,y;
};
long long cross(Point a,Point b,Point c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
using Triangle=array<Point,3>;
bool inside(Point p,const Triangle&t){
long long a=cross(t[0],t[1],p);
long long b=cross(t[1],t[2],p);
long long c=cross(t[2],t[0],p);
return (a>0&&b>0&&c>0)||(a<0&&b<0&&c<0);
}
int main(){
// Compute the exact archive answer using the method explained above.
int n;
cin>>n;
vector<Triangle>triangles(n);
for(auto&t:triangles){
for(auto&p:t){
cin>>p.x>>p.y;
}
}
sort(triangles.begin(),triangles.end(),[](const Triangle&a,const Triangle&b){
return llabs(cross(a[0],a[1],a[2]))<llabs(cross(b[0],b[1],b[2]));
});
vector<int>dp(n,1);
int answer=1;
for(int j=0;j<n;j++){
for(int i=0;i<j;i++){
bool contained=true;
for(Point p:triangles[i]){
contained=contained&&inside(p,triangles[j]);
}
if(contained){
dp[j]=max(dp[j],dp[i]+1);
}
}
answer=max(answer,dp[j]);
}
cout<<answer<<'\n';
}