Intersection of Right Triangles
National Olympiad — National round
Submission name: triangles.cpp
Problem summary
Each triangle has vertices (x,y), (x+a,y), (x,y+b). Find the area common to two such closed triangles.
Input
Two lines, each containing x y a b.
Output
The intersection area rounded to three digits after the decimal point.
Constraints
All eight input integers are positive and at most 10,000.
Worked example
An independently prepared example for this explanation.
Input
1 1 4 4 2 1 4 4
Output
4.500
Solution analysis
- Represent the first triangle as a counterclockwise polygon.
- Clip it against the three inward half-planes of the second triangle using Sutherland–Hodgman clipping.
- For an edge crossing a boundary, interpolate its exact crossing parameter from signed cross products. Apply the shoelace formula to the surviving polygon.
Why it works
A triangle is the intersection of its three inward half-planes. Each clipping step retains precisely the portion of the current convex polygon inside one half-plane, so the final polygon is exactly the intersection.
Watch out. A touch at a point or edge has zero area. Use floating point for intersection coordinates, not integer division.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<cmath>
#include<iomanip>
#include<cstdlib>
#include<iterator>
using namespace std;
struct P{
long double x,y;
P operator+(P b){
return {x+b.x,y+b.y};
}
P operator-(P b){
return {x-b.x,y-b.y};
}
P operator*(long double t){
return {x*t,y*t};
}
};
long double cross(P a,P b){
return a.x*b.y-a.y*b.x;
}
vector<P>read(){
long double x,y,a,b;
cin>>x>>y>>a>>b;
return {{x,y},{x+a,y},{x,y+b}};
}
int main(){
auto poly=read(),q=read();
for(int i=0;i<3;i++){
P a=q[i],b=q[(i+1)%3];
vector<P>next;
for(int j=0;j<(int)poly.size();j++){
P s=poly[j],t=poly[(j+1)%poly.size()];
long double u=cross(b-a,s-a),v=cross(b-a,t-a);
bool inS=u>=0,inT=v>=0;
if(inS){
next.push_back(s);
}
if(inS!=inT){
next.push_back(s+(t-s)*(u/(u-v))); // Boundary crossing.
}
}
poly=next;
}
long double area=0;
for(int i=0;i<(int)poly.size();i++){
area+=cross(poly[i],poly[(i+1)%poly.size()]);
}
cout<<fixed<<setprecision(3)<<abs(area)/2<<'\n';
}