Laser Cutting Machine
National Olympiad — Municipal round (2018 season)
Submission name: cla.cpp
Problem summary
A cutting program describes a closed simple orthogonal polygon. A positive integer cuts that distance forward; + turns left 90 degrees and − turns right 90 degrees. Compute the area enclosed. A turn may precede the first cut.
Input
One command string without separators.
Output
The integer area.
Constraints
String length ≤ 12,000; cut lengths ≤ 2^15; the polygon fits in a square of side 2^15. Nonconsecutive cuts have no common point.
Worked example
Official sample, transcribed with whitespace restored from the PDF.
Input
100+40+40+20-20-20+40+40
Output
3600
Solution analysis
- Choose the initial position (0,0) and initial direction east. Translation and rotation do not affect area. Parse each maximal digit block as a distance, and update the direction immediately on a + or − command, including an optional initial turn.
- For every movement from (x,y) to (u,v), add x·v−y·u to twice the signed polygon area. The path is guaranteed closed and simple, so the absolute value of the final sum divided by two is its area. Horizontal and vertical integer sides ensure an integer answer.
- In the sample the successive vertices are (0,0),(100,0),(100,40),(60,40),(60,20),(40,20),(40,40),(0,40),(0,0). The signed cross products sum to 7200, so the area is 3600. An initial + or − only rotates this shape and preserves the result.
Why it works
Parsing reproduces every cut and turn, hence the polygon boundary. The shoelace formula states that half the absolute sum of consecutive vertex cross products equals the area of a simple closed polygon. Every boundary edge contributes exactly once, so the computed result is the required area.
Watch out. Both turning directions are supported, including an initial turn. Take the absolute area and use 64-bit cross products.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Parsing reproduces every cut and turn, hence the polygon boundary. The shoelace formula
// states that half the absolute sum of consecutive vertex cross products equals the area of a simple
// closed polygon.
#include<iostream>
#include<string>
#include<cctype>
#include<cstdlib>
using namespace std;
int main(){
string program;
cin>>program;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
int direction=0;
long long x=0,y=0,twiceArea=0;
for(int i=0;i<int(program.size());){
if(program[i]=='+'||program[i]=='-'){
direction=(direction+(program[i]=='+'?1:3))%4;
++i;
continue;
}
int distance=0;
while(i<int(program.size())&&isdigit(static_cast<unsigned char>(program[i]))){
distance=distance*10+program[i++]-'0';
}
long long nx=x+dx[direction]*distance;
long long ny=y+dy[direction]*distance;
twiceArea+=x*ny-y*nx;
x=nx;
y=ny;
}
cout<<llabs(twiceArea)/2<<'\n';
}