Polygon Representation and Properties

A polygon is an ordered closed boundary, not just a bag of points. The order tells us which vertices are connected and which region is enclosed. Understanding this representation is essential before computing areas, testing membership or constructing hulls. The program reads a promised simple polygon, computes its perimeter and reports its orientation in a Cartesian coordinate system.

Prerequisites: Points and Vectors; Cross Product; cyclic indexing.

Build the idea

1. Represent the cyclic boundary

   Store n vertices p[0]…p[n−1]. Edge i joins p[i] to p[(i+1)%n], so the last edge returns to the first. The input omits a duplicated closing vertex. A simple polygon has no self-intersections except adjacent edges sharing their endpoint. We require distinct vertices and nonzero area; validity is an input promise, not something the perimeter loop proves.

2. Distinguish shape classes

   A convex polygon contains the entire segment joining any two of its points. A concave simple polygon has an inward indentation and can have reflex angles above 180 degrees. Convexity allows stronger query algorithms, but perimeter and shoelace area work for every simple polygon. An unordered point set must first be given a boundary; sorting arbitrarily does not generally recover its intended polygon.

   $$\mathrm{perimeter}=\Sigma \mathrm{distance}\left(p\right[i],p[(i+1)\mathrm{mod}n\left]\right)$$

3. Accumulate the perimeter

   Each edge contributes the Euclidean distance between its endpoints. Add all n contributions, including the closing edge. hypotl uses the coordinate differences and returns a floating approximation. Unlike area, perimeter is unchanged when vertex order is reversed. Omitting the last edge is easy to spot on a triangle: only two sides would be counted.

4. Determine orientation

   The signed sum of cross products of consecutive position vectors is twice the oriented area. Positive means counterclockwise, negative clockwise, with y increasing upward. A zero sum does not certify a meaningful simple region and falls outside the positive-area promise. Self-crossing paths may have cancellations; do not use the sign as proof of simplicity.

5. Walk around the sample

   Vertices (0,0),(3,0),(3,4),(0,4) form a counterclockwise rectangle. Edge lengths are 3,4,3,4, giving perimeter 14. The signed doubled area is 24. Each loop iteration reads only one cyclic edge, while the vector stores all vertices so the final endpoint can wrap back to p[0].

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

#include<iostream>
#include<vector>
#include<cmath>
#include<iomanip>
struct Point{
    long long x,y;
};
int main(){
    int n;
    std::cin>>n;
    std::vector<Point>p(n);
    for(auto&a:p){
        std::cin>>a.x>>a.y;
    }
    long long signedDoubleArea=0;
    long double perimeter=0;
    // Modulo closes the boundary; do not omit the last-to-first edge.
    for(int i=0;i<n;++i){
        Point a=p[i],b=p[(i+1)%n];
        signedDoubleArea+=a.x*b.y-a.y*b.x; // Bound: n<=100000, |coordinate|<=10^6.
        perimeter+=std::hypotl(b.x-a.x,b.y-a.y);
    }
    std::cout<<(signedDoubleArea>0?"COUNTERCLOCKWISE"
                            :signedDoubleArea<0?"CLOCKWISE"
                                                :"ZERO AREA")
                <<'\n';
    std::cout<<std::fixed<<std::setprecision(6)<<perimeter<<'\n';
}

Complexity analysis

O(n) time and O(n) storage for the vertex vector. Orientation and perimeter share one edge scan. The signed cross sum is bounded in magnitude by 2·n·10^12≤2·10^17, fitting long long.

Example input and output

Read n (3..100000), then a simple nonzero-area polygon in boundary order, without repeated closing vertex. Integer coordinates are within ±10^6. Print orientation and perimeter to six decimals.

Input

4
0 0
3 0
3 4
0 4

Output

COUNTERCLOCKWISE
14.000000

The four sides have lengths 3,4,3,4, and the ordered boundary keeps the interior on the left.

Practical applications

Use ordered polygons for fences, regions and planar boundaries. Convex hull constructs a specific convex boundary from unordered points; it does not reconstruct an arbitrary concave outline. The next lesson derives the area sum used here.

Check your understanding

Which edge closes the stored polygon?

Put it into practice

Reverse the rectangle vertex order and compare outputs.