题解：P16165 [ICPC 2015 NAIPC] Canyon Mapping

lailai0916 · 2026-08-31 06:49:19 · 题解

题意简述

给定一个简单多边形。用恰好 k 个边长相同、平行于坐标轴的正方形覆盖整个多边形，求最小边长。正方形可以重叠。

解题思路

二分答案。设当前判断的边长为 d。

允许重叠，因此不足 k 个时可以重复放置已有正方形。判断能否使用至多 k 个正方形即可。

先说明只覆盖多边形边界已经足够。考虑至多三个正方形的一个连通分量。若两两相交图是一棵树，则逐个加入正方形时，每次交集都是矩形，因而不会形成洞。若三个正方形两两相交，轴对齐矩形的 Helly 性质说明三者有公共点。整个并集关于该点星形，也没有洞。

多边形边界是连通的，只会落在正方形并集的同一个连通分量内。该分量没有洞。若边界已被覆盖，边界围成的内部也不可能留在并集外。因此，只需维护尚未覆盖的边界线段。

对当前线段集求包围盒。若包围盒的宽和高都不超过 d，一个正方形即可覆盖全部线段。

否则考虑包围盒下侧宽为 d 的条带。取落在条带内的所有线段部分，再求它们横坐标的最小值与最大值。贴住条带下边界的正方形只有两种必要位置：贴住这些线段部分的最左端，或贴住最右端。

对上、左、右三个方向同理。每层递归一共枚举八个正方形。

这里使用极端方形引理。设线段集可被至多三个等大轴对齐正方形覆盖，但不能被一个正方形覆盖。它必有一种可行覆盖，其中一个正方形恰为上述八种位置之一。删去它覆盖的部分后，剩余线段仍能由其余正方形覆盖。

证明该引理时，先删去可有可无的正方形。取一个覆盖包围盒某条边界极值的正方形，将它向该边界平移，途中不会失去任何线段点。再沿垂直方向平移，直至碰到条带内线段的一个端点。

若它能到达条带的某一端，就得到对应的规范位置。否则，条带两端分别存在只能由另外两个正方形保留的线段。由于总数不超过三个，这两个正方形已经分别占据条带两端。改取其中一个正方形，从与条带垂直的包围盒边界执行同样的平移，必然到达一个端点。否则还需要第四个正方形阻挡另一端，与数量限制矛盾。故八种位置至少有一种不会破坏可行性。

这个论证对递归中产生的碎线段同样成立。于是枚举八种位置是完备的。

从一条线段中删去一个正方形时，将线段参数区间分别与正方形的横、纵坐标范围求交。被覆盖部分仍是一个区间，剩余部分至多分裂成两条线段。

三个正方形无法形成洞，是边界判定能够代表面积判定的关键。若允许四个正方形，四者可能围出一个洞，上述递归便不再正确。

每次可行性判断最多递归三层，每层枚举八个位置。线段数至多按常数倍增加，因此一次判断的复杂度为 O(8^k n)。二分固定进行 100 轮，空间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

const long double eps=1e-15L;
const long double inf=1e100L;
struct Point
{
    long double x;
    long double y;
};
struct Segment
{
    Point a;
    Point b;
};
struct Range
{
    long double low;
    long double high;
};
Point get_point(const Segment &segment,long double ratio)
{
    Point point;
    point.x=segment.a.x+(segment.b.x-segment.a.x)*ratio;
    point.y=segment.a.y+(segment.b.y-segment.a.y)*ratio;
    return point;
}
array<long double,4> get_bounds(const vector<Segment> &segments)
{
    array<long double,4> bounds={inf,inf,-inf,-inf};
    for(const Segment &segment:segments)
    {
        bounds[0]=min(bounds[0],min(segment.a.x,segment.b.x));
        bounds[1]=min(bounds[1],min(segment.a.y,segment.b.y));
        bounds[2]=max(bounds[2],max(segment.a.x,segment.b.x));
        bounds[3]=max(bounds[3],max(segment.a.y,segment.b.y));
    }
    return bounds;
}
bool clip_interval(long double start,long double finish,long double low,long double high,long double &left,long double &right)
{
    long double direction=finish-start;
    if(fabsl(direction)<=eps)
    {
        if(start<low-eps||start>high+eps)
            return 0;
        return 1;
    }
    long double first=(low-start)/direction;
    long double second=(high-start)/direction;
    if(first>second)
        swap(first,second);
    left=max(left,first);
    right=min(right,second);
    return left<=right+eps;
}
vector<Segment> remove_square(const vector<Segment> &segments,long double left_x,long double bottom_y,long double length)
{
    vector<Segment> result;
    long double right_x=left_x+length;
    long double top_y=bottom_y+length;
    for(const Segment &segment:segments)
    {
        long double left=0;
        long double right=1;
        if(!clip_interval(segment.a.x,segment.b.x,left_x,right_x,left,right)||!clip_interval(segment.a.y,segment.b.y,bottom_y,top_y,left,right))
        {
            result.push_back(segment);
            continue;
        }
        if(left>right)
        {
            result.push_back(segment);
            continue;
        }
        left=max(left,(long double)0);
        right=min(right,(long double)1);
        if(left>eps)
            result.push_back({segment.a,get_point(segment,left)});
        if(right<1-eps)
            result.push_back({get_point(segment,right),segment.b});
    }
    return result;
}
Range get_strip_range(const vector<Segment> &segments,int side,long double boundary)
{
    long double low=inf;
    long double high=-inf;
    for(const Segment &segment:segments)
    {
        long double start;
        long double finish;
        long double limit=boundary;
        if(side<2)
        {
            start=segment.a.y;
            finish=segment.b.y;
        }
        else
        {
            start=segment.a.x;
            finish=segment.b.x;
        }
        if(side==1||side==3)
        {
            start=-start;
            finish=-finish;
            limit=-limit;
        }
        if(start>limit+eps&&finish>limit+eps)
            continue;
        long double left=0;
        long double right=1;
        if(start>limit)
            left=(limit-start)/(finish-start);
        if(finish>limit)
            right=(limit-start)/(finish-start);
        Point first=get_point(segment,left);
        Point second=get_point(segment,right);
        if(side<2)
        {
            low=min(low,min(first.x,second.x));
            high=max(high,max(first.x,second.x));
        }
        else
        {
            low=min(low,min(first.y,second.y));
            high=max(high,max(first.y,second.y));
        }
    }
    return {low,high};
}
bool possible(const vector<Segment> &segments,int maps,long double length)
{
    if(segments.empty())
        return 1;
    if(maps==0)
        return 0;
    array<long double,4> bounds=get_bounds(segments);
    if(bounds[2]-bounds[0]<=length+eps&&bounds[3]-bounds[1]<=length+eps)
        return 1;
    if(maps==1)
        return 0;
    for(int i=0;i<4;i++)
    {
        long double boundary;
        if(i==0)
            boundary=bounds[1]+length;
        else if(i==1)
            boundary=bounds[3]-length;
        else if(i==2)
            boundary=bounds[0]+length;
        else
            boundary=bounds[2]-length;
        Range range=get_strip_range(segments,i,boundary);
        for(int j=0;j<2;j++)
        {
            long double left_x;
            long double bottom_y;
            if(i<2)
            {
                left_x=j==0?range.low:range.high-length;
                bottom_y=i==0?bounds[1]:bounds[3]-length;
            }
            else
            {
                left_x=i==2?bounds[0]:bounds[2]-length;
                bottom_y=j==0?range.low:range.high-length;
            }
            vector<Segment> remaining=remove_square(segments,left_x,bottom_y,length);
            if(possible(remaining,maps-1,length))
                return 1;
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    int k;
    cin>>n>>k;
    vector<Point> points(n);
    for(int i=0;i<n;i++)
        cin>>points[i].x>>points[i].y;
    vector<Segment> segments;
    for(int i=0;i<n;i++)
        segments.push_back({points[i],points[(i+1)%n]});
    array<long double,4> bounds=get_bounds(segments);
    long double low=0;
    long double high=max(bounds[2]-bounds[0],bounds[3]-bounds[1]);
    for(int i=0;i<100;i++)
    {
        long double middle=(low+high)/2;
        if(possible(segments,k,middle))
            high=middle;
        else
            low=middle;
    }
    cout<<fixed<<setprecision(2)<<high<<'\n';
    return 0;
}