Minesweeper Fence
National Olympiad — National round (2009 season)
Submission name: msweeper.cpp
Problem summary
N circular mines have the same radius R and may overlap. Find the minimum length of one closed tape enclosing all mines.
Input
N R, then N integer center coordinates x y.
Output
The minimum enclosing perimeter, with exactly three digits after the decimal point.
Constraints
1 ≤ N ≤ 10000; 1 ≤ R ≤ 41; −20000 < x,y < 20000.
Worked example
An independently prepared example for this explanation.
Input
8 1 1 4 3 2 7 9 5 4 9 5 6 7 9 1 11 8
Output
34.408
Solution analysis
- A taut enclosing tape follows the boundary of the convex hull of all disks. Because their radii are equal, this hull is the convex hull of the centers expanded by a disk of radius R.
- Compute the center hull using a sorted monotone chain. Its straight edges contribute their usual lengths. The rounding arcs together turn through one full revolution and therefore contribute 2πR.
- In the sample the hull of the centers has perimeter about 28.1248. Adding 2π gives 34.408 after rounding. One distinct center gives just a circle; two centers give a capsule with twice their distance plus 2πR.
Why it works
Any nonconvex detour of an enclosing curve can be shortened by a straight chord, so a shortest enclosure is convex. Equal-radius expansion preserves each hull-edge length and replaces vertex turns by radius-R arcs. The sum of convex exterior angles is 2π, hence the claimed perimeter. The monotone-chain cross-product rule constructs exactly that center hull.
Watch out. Remove duplicate centers. Handle one-point and collinear hulls; for two endpoints the polygonal perimeter must count the segment twice.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<vector>
using namespace std;
struct Point{
long long x,y;
bool operator<(const Point&other)const{
return x!=other.x?x<other.x:y<other.y;
}
bool operator==(const Point&other)const{
return x==other.x&&y==other.y;
}
};
long long cross(Point a,Point b,Point c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int main(){
// Compute the exact archive answer using the method explained above.
int n,radius;
cin>>n>>radius;
vector<Point>points(n);
for(Point&p:points){
cin>>p.x>>p.y;
}
sort(points.begin(),points.end());
points.erase(unique(points.begin(),points.end()),points.end());
vector<Point>hull;
for(Point p:points){
while(hull.size()>=2&&cross(hull[hull.size()-2],hull.back(),p)<=0){
hull.pop_back();
}
hull.push_back(p);
}
size_t lower=hull.size();
for(int i=static_cast<int>(points.size())-2;i>=0;i--){
while(hull.size()>lower&&cross(hull[hull.size()-2],hull.back(),points[i])<=0){
hull.pop_back();
}
hull.push_back(points[i]);
}
if(hull.size()>1){
hull.pop_back();
}
long double answer=2*acosl(-1.0L)*radius;
for(size_t i=0;i<hull.size();i++){
Point a=hull[i];
Point b=hull[(i+1)%hull.size()];
answer+=hypotl(static_cast<long double>(a.x-b.x),static_cast<long double>(a.y-b.y));
}
cout<<fixed<<setprecision(3)<<answer<<'\n';
}