Triangle Area by Subtraction
National Olympiad — Municipal round
Submission name: lica.cpp
Problem summary
Three integer-coordinate points form a triangle. Find its area. If an axis-parallel side allows direct base-times-height computation, report zero auxiliary triangles. Otherwise use the smallest axis-parallel enclosing rectangle and subtract the nonzero right triangles outside the given triangle; report their areas in increasing order.
Input
Three lines, each containing x y for one vertex.
Output
Triangle area on the first line. On the second line, 0 if direct computation is possible; otherwise the number of auxiliary triangles, followed on the next line by their sorted areas. Print every area with one digit after the decimal point.
Constraints
Coordinates are integers in [−100,100].
Worked example
An independently prepared example for this explanation.
Input
0 0 4 1 1 3
Output
5.5 3 1.5 2.0 3.0
Solution analysis
- Use the absolute cross product to compute twice the area exactly.
- If two vertices share an x-coordinate or y-coordinate, their side is an axis-parallel base and no enclosing rectangle is needed.
- Otherwise each side cuts off a right triangle of area |dx·dy|/2 from the bounding rectangle. Sort the three areas.
Why it works
With no horizontal or vertical side, the three complementary corner triangles partition the enclosing rectangle outside the triangle. Their legs are the coordinate differences of the corresponding side endpoints.
Watch out. Do not report auxiliary triangles when there is a horizontal or vertical base, including a non-right triangle with such a base.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: With no horizontal or vertical side, the three complementary corner triangles partition
// the enclosing rectangle outside the triangle. Their legs are the coordinate differences of the
// corresponding side endpoints.
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
using namespace std;
int main(){
long long x[3],y[3];
for(int i=0;i<3;i++){
cin>>x[i]>>y[i];
}
long long area=llabs((x[1]-x[0])*(y[2]-y[0])-(y[1]-y[0])*(x[2]-x[0]));
bool direct=false;
vector<long long>a;
for(int i=0;i<3;i++){
int j=(i+1)%3;
direct|=x[i]==x[j]||y[i]==y[j];
a.push_back(llabs((x[i]-x[j])*(y[i]-y[j])));
}
cout<<fixed<<setprecision(1)<<area/2.0<<'\n';
if(direct){
cout<<0<<'\n';
}
else{
sort(a.begin(),a.end());
cout<<3<<'\n';
for(auto z:a){
cout<<z/2.0<<' ';
}
cout<<'\n';
}
}