https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=616&page=show_problem&problem=4567

  1. 转换视角:所有的输出均可视为一条水平线段的两端点。故保存水平线段即可。
  2. 扫一遍,维护上下两凸包当前的最右端的线段属性值。(详见代码注释)
/*0ms,608KB*/

#define MT(a, b, c) make_pair(make_pair(a, b), c)
#define LX first.first
#define RX first.second
#define Y second

map<int, vector<int> > p;
vector<p3> low, upp; /// 转换视角:所有的输出均可视为一条水平线段的两端点。故保存水平线段即可

/// 注意,以下注释均基于题目所给图在逆时针旋转90度后得到的图
int main()
{
    int n, cas = 0, i, x, y, miny, maxy;
    miter it;
    while (scanf("%d", &n), n)
    {
        p.clear(), low.clear(), upp.clear();
        For(i, n) SII(x, y), p[x].PB(y);
        for (it = p.begin(); it != p.end(); ++it)
        {
            x = it->first;
            miny = *min_element(all(it->second));
            maxy = *max_element(all(it->second)) + 9;
            if (it == p.begin())
            {
                low.PB(MT(x, x + 9, miny));
                upp.PB(MT(x, x + 9, maxy));
            }
            else
            {
                /// 求下凸包
             while (low.size() >= 2 && low.back().Y > miny && low.back().Y > low[low.size() - 2].Y)
                    low.pop_back(); /// 若边界为“上升-下降”型,则抹掉凸出来的那部分。这里的思想同Graham-Scan算法
             if (low.back().Y == miny) low.back().RX = x + 9; /// 平
             else if (miny < low.back().Y) /// 降
             {
                    low.back().RX = x;
                    low.PB(MT(x, x + 9, miny));
                }
                else low.PB(MT(low.back().RX, x + 9, miny)); /// 升
             /// 求上凸包
             while (upp.size() >= 2 && upp.back().Y < maxy && upp.back().Y < upp[upp.size() - 2].Y)
                    upp.pop_back();
                if (upp.back().Y == maxy)upp.back().RX = x + 9;
                else if (maxy > upp.back().Y)
                {
                    upp.back().RX = x;
                    upp.PB(MT(x, x + 9, maxy));
                }
                else upp.PB(MT(upp.back().RX, x + 9, maxy));
            }
        }
        ///
     printf("Case %d: ", ++cas);
        printf("%d %d", low[0].LX, low[0].Y);
        For(i, upp.size())
        {
            printf(" %d %d", upp[i].LX, upp[i].Y);
            printf(" %d %d", upp[i].RX, upp[i].Y);
        }
        rForr(i, low.size() - 1, 1)
        {
            printf(" %d %d", low[i].RX, low[i].Y);
            printf(" %d %d", low[i].LX, low[i].Y);
        }
        printf(" %d %d\n", low[0].RX, low[0].Y);
    }
    return 0;
}

Comments

comments powered by Disqus