自动搬运

查看原文

来自洛谷，原作者为

	Rakuteni Disguiser is me

搬运于2025-08-24 22:30:06，当前版本为作者最后更新于2023-08-01 11:20:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有一些算法（严格意义上来说，不是算法吧（大佬求教））（本蒻苟现学的）

凸包算法：通过 Graham 扫描算法求解点集的凸包。用点集的极角排序和栈的数据结构来构建凸包。

极角排序：在计算高收益配置时，将凸包上的点按照相对于参考点的极角进行排序。确定过道的连接顺序。

集合和映射：使用集合和映射来记录极角的出现次数。集合用于存储极角，保证极角的唯一性和排序。映射用于记录每个极角的出现次数。

然后稍微解释一下（本蒻苟不保证一定对哈，恳请大佬改正）

首先呢，咱通过凸包算法求解给定老虎机坐标点集的凸包。凸包它就是一个包围所有老虎机的最小凸多边形。

接下来呢，如果凸包它的点数等于老虎机的总数，那不就说明所有老虎机都在凸包上，此时咱就直接输出结果。

那么如果凸包的点数小于老虎机的总数，那就说明存在老虎机在凸包内部。所以咱需要进一步计算高收益配置的大小和个数。

因此，咱首先找到凸包上的一个点作为参考点 $c$，并按照相对于 $c$ 的极角对凸包上的点进行排序。

然后构建一个集合 $s$ 来存储极角，并根据极角的大小进行排序。然后遍历凸包外部的点，计算它们与 $c$ 的极角，并将极角加入集合 $s$ 中。

然后再构建一个映射 $m$ 来记录每个极角的出现次数。根据集合 $s$ 中的极角顺序，更新映射 $m$ 中每个极角的出现次数。

最后啊，根据映射 $m$ 中的信息，确定高收益配置的大小和个数。具体做法是根据极角的出现次数，确定哪些过道需要建立连接，从而形成高收益配置。

然后咱就输出就 OK 咯。

然后是代码的解释？

咱先构建一个结构体 $Pt$ 存点，$x$ 表示 $x$ 坐标，$y$ 表示 $y$ 坐标，$id$ 编号。然后让 $Pt$ 结构体重载了一些运算符，方便一下子（偷懒）。

然后这个函数 cross(Pt a, Pt b) 是算一下 $a$ 和 $b$ 的叉积。它在咱后续的计算中用于判断点的位置关系。

然后另外一个函数 cross(Pt a, Pt b, Pt c) 它是三个点 $a$, $b$, $c$ 组成的两个向量的叉积的计算的函数（好别扭）。然后这个函数在凸包的计算中是会被用到的。

接下来函数 convex_hull(vector<Pt> p) 是用于计算给定点集 $p$ 的凸包。

• 首先，点集 $p$ 被按照 $Cmp$ 排序。
• 排序后，使用 Graham's scan 算法寻找凸包。具体做法是遍历排序后的点集，如果遇到新点的加入会使凸包不再是凸多边形，则将之前的点移除，直到凸包再次满足凸多边形性质。
• 函数返回计算得到的凸包 $a$。 如果计算得到的凸包 $a$ 的大小等于原始老虎机集合 $b$ 的大小，那么说明所有老虎机都在凸包上，即没有内部的老虎机。在这种情况下，咱就输出 $3$ 表示只有一个高利润配置，然后输出凸包上的老虎机数量和总老虎机数量就行了。

要不然它就是内部老虎机。

然后我们先找到凸包上两个最远的点，并将它们作为第一组枢纽机。

然后，将剩余的老虎机分为不同的区域，根据它们是否被两个枢纽机包围。这些区域将构成高利润配置的一部分。

计算高利润配置的数量和每个配置涉及的老虎机数量。

最后，输出 $4$ 表示存在多个高利润配置，然后输出凸包内的老虎机数量（不包括枢纽机），以及高利润配置中老虎机的总数量。

最后贴一下代码吧

#include <bits/stdc++.h>
using namespace std;
struct Pt{
    long long x,y,id;
	Pt operator-(){return{-x,-y};}
	Pt operator+(const Pt&p){return{x+p.x,y+p.y};}
	Pt operator-(const Pt&p){return{x-p.x,y-p.y};}
	Pt operator*(long long d){return {x*d,y*d};}
	Pt operator/(long long d){return {x/d,y/d};}
    bool operator<(const Pt&a)const{ return id<a.id; }
    friend ostream &operator<<(ostream &os, const Pt&a){
        os<<a.x<<' '<<a.y;
        return os;
    }
    friend istream &operator>>(istream &is, Pt&a){
        is>>a.x>>a.y;
        return is;
    }
};
struct Cmp{ bool operator()(const Pt&a, const Pt&b)const{ return (a.x != b.x) ? a.x < b.x : a.y < b.y; } };
long long cross(Pt a, Pt b){ return a.x*b.y-a.y*b.x; }
long long cross(Pt a, Pt b, Pt c){ return cross(b-a,c-a); }
vector<Pt> convex_hull(vector<Pt> p) {
	vector<Pt> r(2 * p.size() + 14);
	long long K = 0;
	sort(p.begin(), p.end(), Cmp());
	for(Pt e:p){
		while (K >= 2 && cross(r[K-1]-r[K-2], e-r[K-2]) <= 0) K--;
		r[K++] = e;
	}
	for(long long i=p.size()-2, T=K+1; i>=0; i--){
		while (K >= T && cross(r[K-1]-r[K-2], p[i]-r[K-2]) <= 0) K--;
		r[K++] = p[i];
	}
	r.resize(K);
	r.pop_back();
	return r;
}
Pt c;
bool cmp(Pt &a,Pt &b){
    Pt da=a-c;
    Pt db=b-c;
    double aa=atan2(da.y,da.x);
    double bb=atan2(db.y,db.x);
    return aa<bb;
}
#define TAU (2*M_PI)
int main(){
    long long N;cin>>N;
    vector<Pt> b(N);
    long long idx=0;
    for(Pt &p:b){ cin>>p; p.id=idx++; }
    vector<Pt> a=convex_hull(b);
    if(a.size()==b.size()){
        cout<<"3 "<<(N-2)<<" "<<N<<endl;
    }else{
        c={0,0,1<<30};
        for(Pt &d:a)if(d.id<c.id)c=d;
        set<double> s;
        map<double,long long> m;
        for(Pt &d:a)s.insert(fmod(atan2(d.y-c.y,d.x-c.x)+TAU,TAU));
        s.insert((*s.begin())+TAU);
        set<Pt> rest(b.begin(),b.end());
        for(Pt &d:a)rest.erase(d);
        for(double w:s)m[w]=0;
        for(const Pt &d:rest){
            double q=*s.lower_bound(fmod(atan2(d.y-c.y,d.x-c.x)+TAU,TAU));
            if(q>=TAU)q-=TAU;
            m[q]++;
        }
        long long M=a.size()-1;
        vector<bool> f(M,0);
        long long idx=0;
        for(const pair<double,long long> &p:m){
            double value=p.first;
            long long count=p.second;
            if(count){
                f[idx]=1;
                f[(idx+1)%M]=1;
            }
            idx++;
        }
        long long cnt=rest.size();
        long long res=1+cnt;
        for(int i=0; i<M; ++i){ res+=f[i]; }
        cout<<"4 "<<cnt<<" "<<res<<endl;
    }
}