Introduction to Computational Geometry

Computational geometry turns spatial questions into algorithms: do paths cross, which sensor is nearest, what boundary encloses a set, or how much area is covered? The challenge is translating a diagram into predicates that stay correct on awkward inputs. This first program finds a bounding rectangle, an intentionally small task that exposes representations, exact arithmetic and approximate measurements before we build more complicated algorithms.

Prerequisites: Integer arithmetic, loops, structs and basic coordinate geometry.

Build the idea

1. Objects and coordinates

   A point is a location (x,y); a vector is a displacement. An infinite line has a direction, a segment also has endpoints, a circle has a center and radius, and a polygon has an ordered boundary. We use Cartesian coordinates: x increases rightward and y upward. A screen canvas often reverses y, so a visually clockwise turn there may be counterclockwise in this convention.

2. Choose a numerical model

   Integer coordinates permit exact equality, orientation and squared-distance comparisons if every intermediate fits. Floating-point coordinates approximate real values and need error analysis. A long long is not universally sufficient: subtracting opposite extreme values can overflow before multiplication. Under |coordinate|≤10^6, differences fit 2·10^6 and a bounding-box area fits 4·10^12. Wider ranges may require __int128 on supporting GCC/Clang targets; that extension is not portable C++17.

   $$A=(\mathrm{maxX}-\mathrm{minX})·(\mathrm{maxY}-\mathrm{minY})$$

3. Maintain a bounding rectangle

   After processing some points, minX and maxX are their smallest and largest x-coordinates, with analogous y-values. Initialize all four extrema from the first point, not zero. Reading another point changes only these extrema. The invariant proves both containment and minimality among axis-aligned rectangles: any containing rectangle must reach every coordinate extreme.

4. Trace a coordinate example

   For (−2,1),(3,4),(1,−1), the extremes are x∈[−2,3], y∈[−1,4]. The rectangle has width 5, height 5 and area 25; its diagonal is √50≈7.071068. These are rectangle measurements, not the area or diameter of the three-point set. Distinguishing the object being measured prevents a common modeling error.

5. Read the implementation and its contract

   The Point structure stores one integer location. Only one point and four extrema are retained, so the algorithm can stream the input. The area is printed exactly; hypotl and six decimal places produce an approximate diagonal. One point or collinear points are valid and may give zero area. The positive n requirement avoids initializing from nonexistent data.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
struct Point{
    long long x,y;
};
int main(){
    int n;
    std::cin>>n; // 1 <= n <= 100000, integer coordinates within +/- 10^6.
    Point p;
    std::cin>>p.x>>p.y;
    long long minX=p.x,maxX=p.x,minY=p.y,maxY=p.y;
    for(int i=1;i<n;++i){
        std::cin>>p.x>>p.y;
        minX=std::min(minX,p.x);
        maxX=std::max(maxX,p.x);
        minY=std::min(minY,p.y);
        maxY=std::max(maxY,p.y);
    }
    long long width=maxX-minX,height=maxY-minY;
    std::cout<<minX<<' '<<minY<<' '<<maxX<<' '<<maxY<<'\n';
    std::cout<<width*height<<'\n'; // At most 4*10^12, exact in long long.
    std::cout<<std::fixed<<std::setprecision(6)<<std::hypotl(width,height)<<'\n';
}

Complexity analysis

O(n) time because each point updates four extrema. O(1) auxiliary space; input is streamed. Square root is evaluated once after exact integer work.

Example input and output

Read n (1..100000), then n integer pairs with each coordinate in [−10^6,10^6]. Print minX minY maxX maxY, rectangle area, then its approximate diagonal.

Input

3
-2 1
3 4
1 -1

Output

-2 -1 3 4
25
7.071068

The five-by-five box reaches all four coordinate extremes. Its diagonal follows Pythagoras.

Practical applications

Use a box for quick rejection, coordinate normalization and spatial indexing. It is a coarse filter: overlapping boxes do not prove the underlying shapes intersect. Orientation, segment intersection and convex hulls refine these decisions in later lessons.

Check your understanding

Why initialize the extrema from the first input point?

Put it into practice

Test a singleton, repeated points and three points on a vertical line.