Area of a Union of Rotated Squares
Autumn Tournament (2015)
Submission name: squares.cpp
Problem summary
Each square is specified by its centre and one vertex, and may be rotated. Find the area covered by at least one of the squares, rounded to the nearest integer.
Input
N, then N lines centreX centreY vertexX vertexY.
Output
The union area rounded to the nearest integer.
Constraints
1≤N≤9; every given coordinate is an integer in[−50,50]; each square is nondegenerate.
Worked example
Original statement sample.
Input
3 -35 45 -50 50 -15 35 -40 20 -40 30 -30 20
Output
2175
Solution analysis
- Let the vector from the centre to its given vertex be(dx,dy). Rotating it by90° repeatedly gives the four square vertices in counterclockwise order. The area of one square is2(dx²+dy²); do not assume its sides follow the coordinate axes.
- Because there are at most nine squares, use inclusion–exclusion over all nonempty subsets. Intersections of convex polygons remain convex. To intersect with a square, clip the current polygon against each directed side, retaining points on the left of that side and adding line-segment intersection points when an edge crosses it.
- Compute each clipped polygon’s area with the shoelace formula. Add odd-sized subset intersections and subtract even-sized ones, then round once at the end. The sample’s three rotated squares have total union area2175; identical squares or shared boundaries are handled by the same formula without double counting.
Why it works
Half-plane clipping preserves exactly the points lying in all processed half-planes, so after the four sides it yields intersection with the square. Inclusion–exclusion counts a point covered by k squares exactly Σ(−1)^(j+1)C(k,j)=1 times. Integrating these indicator counts proves the area formula.
Watch out. Use counterclockwise vertices and a consistent inside test. Handle empty intersections and parallel edges. Keep long double precision and round only the final union area, not intermediate intersections.
Commented C++17 solution
An independently written complete program with standard headers.
#include<cmath>
#include<iomanip>
#include<iostream>
#include<vector>
using namespace std;
struct Point{
long double x;
long double y;
};
Point operator+(Point a,Point b){
return {a.x+b.x,a.y+b.y};
}
Point operator-(Point a,Point b){
return {a.x-b.x,a.y-b.y};
}
Point operator*(Point a,long double scale){
return {a.x*scale,a.y*scale};
}
long double cross(Point a,Point b){
return a.x*b.y-a.y*b.x;
}
vector<Point>clip(const vector<Point>&polygon,Point a,Point b){
vector<Point>result;
if(polygon.empty()){
return result;
}
for(int i=0;i<static_cast<int>(polygon.size());i++){
Point p=polygon[i];
Point q=polygon[(i+1)%polygon.size()];
long double sideP=cross(b-a,p-a);
long double sideQ=cross(b-a,q-a);
bool insideP=sideP>=-1e-15L;
bool insideQ=sideQ>=-1e-15L;
if(insideP){
result.push_back(p);
}
if(insideP!=insideQ){
// Linear interpolation finds the intersection with the clipping line.
long double ratio=sideP/(sideP-sideQ);
result.push_back(p+(q-p)*ratio);
}
}
return result;
}
long double area(const vector<Point>&polygon){
long double result=0;
for(int i=0;i<static_cast<int>(polygon.size());i++){
result+=cross(polygon[i],polygon[(i+1)%polygon.size()]);
}
return fabsl(result)/2;
}
int main(){
int n;
cin>>n;
vector<vector<Point>>square(n);
for(int i=0;i<n;i++){
Point centre,vertex;
cin>>centre.x>>centre.y>>vertex.x>>vertex.y;
Point offset=vertex-centre;
for(int turn=0;turn<4;turn++){
square[i].push_back(centre+offset);
offset={-offset.y,offset.x};
}
}
long double result=0;
for(int mask=1;mask<(1<<n);mask++){
vector<Point>intersection;
int count=0;
for(int i=0;i<n;i++){
if((mask&(1<<i))==0){
continue;
}
if(count==0){
intersection=square[i];
}
else{
for(int edge=0;edge<4;edge++){
intersection=clip(intersection,square[i][edge],square[i][(edge+1)%4]);
}
}
count++;
}
result+=(count%2==1?1:-1)*area(intersection);
}
cout<<llroundl(result)<<'\n';
}