Comment

SoulPowering...: 2026-05-13 10:27:42

Andrew 单调链算法：


#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int>PII;
typedef long long LL;
const int N=110;
int n;
PII p[N];
LL cross(PII a,PII b,PII c)//叉积很大可能爆int
{
    //(b-a)x(c-a)
    return 1LL *(b.first-a.first)*(c.second-a.second)-
           1LL *(b.second-a.second)*(c.first-a.first);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int m;
    cin>>m;
    for(int round=1;round<=m;round++)
    {
        cout<<"case "<<round<<":\n";
        cin>>n;
        for(int i=0;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            p[i]={x,y};
        }
        sort(p,p+n);
        //将所有点从左至右x排序，x相同则y从小到大
        
        //一定要去重，勿忘，切记！！
        n=unique(p,p+n)-p;

        //vector:
        //  p.erase(unique(p.begin(), p.end()), p.end());
        //  n=p.size();

        //两个数组vector:lower,upper,
        vector<PII>lower,upper;
        
        //lower（凸包下边界）:从左端点一直扫到右端点，
        //（至少存在两点）前两个点与新点cross<=0,右转，则popback，
        //由于要知道倒数第一、倒数第二个点，所以用数组手写栈，直接能拿到
        
        //upper同理，最后去重端点拼在一起
        //再找到最下边的点start，使用(start+i)%size取余操作进行输出
        
        //如果最开始仅有一个或两个点，直接输出：
        if(n==1)
        {
            cout<<p[0].first<<" "<<p[0].second<<"\n";
            continue;
        }
        if(n==2)
        {
            if(p[1].second<p[0].second)
                swap(p[1],p[0]);
            for(int i=0;i<=1;i++)
                cout<<p[i].first<<" "<<p[i].second<<"\n";
            continue;
        }
        //构造lower
        for(int i=0;i<n;i++)
        {
            //弹出
            while(lower.size()>=2&&
            cross(lower[lower.size() - 2],lower[lower.size() - 1],p[i])<=0)
                lower.pop_back();
            //压入栈
            lower.push_back(p[i]);
        }
        for(int i=n-1;i>=0;i--)//++!=--
        {
            //弹出
            while(upper.size()>=2&&
            cross(upper[upper.size() - 2],upper[upper.size() - 1],p[i])<=0)
                upper.pop_back();
            //压入栈
            upper.push_back(p[i]);
        }
        lower.pop_back();
        upper.pop_back();
        
        //拼在一起
        vector<PII>res;
        for(int i=0;i<=lower.size()-1;i++)
            res.push_back(lower[i]);
        for(int i=0;i<=upper.size()-1;i++)
            res.push_back(upper[i]);
            
        int start=0;
        //n为去重后的总点数，res.size()为凸包点数，两者完全不等哈！！！！！！！！！
        for(int i=1;i<res.size();i++)
            if(res[start].second>res[i].second||res[start].second==res[i].second&&res[i].first<res[start].first)
                start=i;
        for(int i=0;i<res.size();i++)
            cout<<res[(start+i)%res.size()].first<<" "<<res[(start+i)%res.size()].second<<"\n";
    }

    
    return 0;
}

chenxuanyu: 2025-04-26 15:59:13

记得加case，血的教训

212050胡昱: 2021-11-02 23:52:57

（不要理我上面那些评论...

212050胡昱: 2021-11-02 23:48:37

1
10 1 2 41 2 12 4 12 53 -1 2 -2 5 92 0 -10 -10 9 1 10 10

这个示例大家可以试一下吗？

212050胡昱: 2021-11-02 23:43:58

感觉示例代码是错的，随便输入了10个点进去（不包括原点），发现示例代码在输出的时候自己添了一个(0, 0)的点...

CyanFish: 2020-10-12 20:43:49

样例过了 ，但是提交结果总是Answer Wrong。对于样例代码，有个小疑问，当给定的点都在一条直线上时，样例代码会输出直线两个端点和（0，0），而我自己写的只会生成直线两个端点，不知道各位大佬是否遇到类似的情况？

201882_taohansi: 2020-09-24 15:48:47

额，是从(4,1)不是(1,4),笔误

201882_taohansi: 2020-09-24 15:47:04

题目表述有误，应将"最下最右点"改为"最下最左点"，否则样例也应从(1,4)开始输出而非(1,1)