老虎机（官方题解+蒻苟解释）

· · 题解

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

凸包算法：通过 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 的凸包。

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

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

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

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

最后，输出 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;
    }
}