2021 RoboCom 世界机器人开发者大赛-本科组（初赛）7-2 芬兰木棋_7-2 芬兰木棋测试点分析

题目：

芬兰木棋（Mölkky，又称芬兰木柱）是源自芬兰的一项运动。哲哲将这个运动改造成了赛博朋克单人版，现在场上一开始有 N 根立起的小木棋（上面分别标有一个非负整数），哲哲投掷一根大木棋去击倒这些小木棋以获得分数。分数规则如下：

• 如果仅击倒 1 根木棋，则得木棋上的分数。
• 如果击倒 2 根或以上的木棋，则只得击倒根数的分数。（例如击倒 5 根，则得 5 分。）

哲哲固定站在 (0,0) 点上，四周放着若干个小木棋 (Xi​,Yi​)，坐标均为整数。每次哲哲可以朝一个方向扔出大木棋，大木棋会打倒这个方向上离哲哲最近的 k 个小木棋。哲哲游戏水平很高超，所以这个 k 可以自由控制。

请问哲哲最多能拿多少分，在获得最多分数的情况下最少需要扔出多少次大木棋？

规则与真实规则有较大出入，真实游玩时请以国际莫尔基组织的规则为准

输入格式:

输入第一行是一个正整数 N (1 ≤ N ≤ 105)，表示场上一开始有 N 个木棋。

接下来 N 行，每行 3 个整数 Xi​,Yi​,Pi​，分别表示木棋放置在 (Xi​,Yi​)，木棋上的分数是 Pi​。坐标在 32 位整数范围内，分数为小于等于 1000 的正整数。

保证 (0,0) 点没有木棋，也没有木棋重叠放置。

输出格式:

输出一行两个数，表示最多分数以及获得最多分数最少需要投掷大木棋多少次。

输入样例:

11
1 2 2
2 4 3
3 6 4
-1 2 2
-2 4 3
-3 6 4
-1 -2 1
-2 -4 1
-3 -6 1
-4 -8 2
2 -1 999

输出样例:

1022 9

思路：

1.将所有在同一个方向的木棋分为一组。

2.用x/y得到斜率，将各象限和坐标轴用数字1-8编号，斜率和编号相等的点为一组，用pair存储。

3.对每组木棋按到原点距离 d=sqrt(x*x+y*y) 从小到大排序。

4.所有的木棋都击倒得到的分数就是最大的，所以只需思考怎样使得扔出次数最少，显然把所有连续的1一次击倒就可以了，这样既没有改变得到的分数，还减少了扔出的次数。

按顺序枚举每组木棋，如果木棋上的数大于1，直接击倒；对于连续的1可以一次性击倒。

代码：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef pair<double,int> pii;
int n,x,y,p,cnt,sum;
double h;
struct node{
    int v;
    double d;
};
bool cmp(node x,node y){
    return x.d<y.d;
}
map<pii,vector<node>> mp;
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        node a;
        pii u;
        cin>>x>>y>>p;
        if(y!=0)//防止出现除以零的情况
        h=x*1.0/y;
        a.v=p;//木棋上的分数
        a.d=sqrt(x*x+y*y);//到原点的距离
        if(x<0&&y>0) {u.first=h,u.second=1;}//斜率，编号
        else if(x==0&&y>0) {u.first=0,u.second=2;}
        else if(x>0&&y>0) {u.first=h,u.second=3;}
        else if(x>0&&y==0) {u.first=0,u.second=4;}
        else if(x>0&&y<0) {u.first=h,u.second=5;}
        else if(x==0&&y<0) {u.first=0,u.second=6;}
        else if(x<0&&y<0) {u.first=h,u.second=7;}
        else if(x<0&&y==0) {u.first=0,u.second=8;}
        mp[u].push_back(a);
    }
    for(auto t:mp)//枚举每个小组
    {
        vector<node> k=t.second;
        sort(k.begin(),k.end(),cmp);//按到原点距离从小到大排序
        for(int i=0;i<k.size();i++)
        {
            if(k[i].v>1)
            {
                cnt++;
                sum+=k[i].v;
            }
            else if(k[i].v==1)
            {
                while(k[i].v==1&&i<k.size())
                {
                    sum++;
                    i++;
                }
                i--;//此时k[i].v已经大于1了，下次循环时还会i++,所以在这里减一
                cnt++;//只击倒了一次
            }
        }
    }
    cout<<sum<<" "<<cnt<<endl;
    return 0;
}