2021 RoboCom 世界机器人开发者大赛-本科组（初赛）7-2 芬兰木棋 (25 分)

芬兰木棋（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）一对互质的整数可以唯一地表示一个斜率，所以这里可以将木棋的(x,y)坐标同时除他们的gcd，变成两个互质的整数，用形如map<pair,vector<pair>>这样的结构存储，就完成了斜率分类。

（2）同个斜率时需区分方向，如果x<0分为左部分，x>0分为右部分，x=0且y>0为y轴上部分,x=0且y<0为y轴下部分，这样就分清方向了。

（3）再把每个方向的坐标进行排序，左右部分按x小到大排序，上下y轴部分按y小到大排序。

（4）枚举每个方向，从前往后枚举，如果有连续的一段木棋的p值全都是1，那么把它们一起击倒得到的收益和分别击倒得到的收益是一样的，可以合并击倒。如果单个木棋的p值大于1，肯定是单独击倒划算，就单独击倒。

最终显然所有的木棋都可以被击倒，最多分数就是所有木棋p值的和，最少投掷次数就根据上述方法贪心求解。

时间复杂度O(nlogn)。   

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
map<PII,vector<PII>> lalg;//左半轴 
map<PII,vector<PII>> ralg;//右半轴 
vector<PII> uxalg,dxalg;//x=0（y轴）上半部分和下半部分
map<PII,int> mw;//分数 
int gcd(int a,int b){
	if(b == 0) return a;
	return gcd(b,a%b);
}
bool cmp(PII a,PII b){
	if(a.first != 0) return a.first < b.first;//x!=0时 
	else return a.second < b.second; 
}
int getcount(vector<PII> &tmp){
	if(!tmp.size()) return 0;
	int count = 0;
	sort(tmp.begin(),tmp.end(),cmp);
	for(int i = 0; i < tmp.size(); i++){
		if(mw[tmp[i]] == 1){
			count++;
			while(i < tmp.size() && mw[tmp[i]] == 1) i++;
			i--;
			continue;
		}else count++;
	}
	return count;
}
int main(){
	int n,fra = 0, count = 0;
	cin>>n;
	for(int i = 0; i < n; i++){
		int x,y,w;
		cin>>x>>y>>w;
		fra += w;
		int g = gcd(x,y);
		PII xl{x/g,y/g};//互质整数为斜率
		PII zb{x,y};//坐标
		if(x > 0) ralg[xl].push_back(zb);
		else if(x < 0) lalg[xl].push_back(zb);
		else if(y > 0) uxalg.push_back(zb);//x=0时上半部分 
		else dxalg.push_back(zb);//x=0时下半部分 
		mw[zb] = w;//zb位置的分数 
	}
	for(auto x:lalg){
		count += getcount(x.second);
	}
	for(auto x:ralg){
		count += getcount(x.second);
	}
	count += getcount(uxalg);
	count += getcount(dxalg);
	cout<<fra<<' '<<count;
	return 0;
}