题意就是坐标系中有n个点,每个点有一个分数
你可以往一条射线上扔球打这些点
(1)打到单个点得对应分值
(2)打到多个点每个得一分
问:最多可以得多少分?要想拿到最高分至少需要打几次?
最多多少分非常容易,所有球都单击,就能得满分
对于打几次,我们可以很容易得出,如果一个球分数大于1,那么就单独打它
如果有连续一堆球分数都为1,那么就一起打掉
骚操作:用哈希表给点分类,map<pii,vector<node>> s
,相当于把属于pii类的映射成一个vector集合
怎么判断哪些点在一条直线上呢?用斜率,但是对于在y轴上的点,斜率不存在,那就特判!
不过这题是射线,从原点出发的射线,所以不能用斜率来分类,那怎么分呢?
用坐标来分类,对于每个点,将(x,y)分别除以gcd(x,y),得到的坐标就可以精确地分类所有的射线
同样,对于x = 0或者y = 0的情况,直接特判!
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int INF = 0x3f3f3f3f;
struct node
{
ll x,y,p;
};
map<pii,vector<node>> s;
bool cmp(node a,node b)
{
return a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;
}
int main()
{
int n;
cin >> n;
ll sum = 0;
while(n --)
{
ll x,y,p;
scanf("%lld %lld %lld",&x,&y,&p);
sum += p;
int a,b,t = abs(__gcd(x,y));
if(x && y)
a = x / t,b = y / t;
else if(!x && y > 0)
a = 0,b = INF;
else if(!x && y < 0)
a = 0,b = -INF;
else if(x > 0 && !y)
a = INF,b = 0;
else if(x < 0 && !y)
a = -INF,b = 0;
s[{a,b}].push_back({x,y,p});
}
int cnt = 0;
for(auto x : s)
{
sort(x.second.begin(),x.second.end(),cmp);
for(int i = 0;i < x.second.size();i ++)
{
if(x.second[i].p == 1)
{
int j = i;
while(x.second[j].p == 1)
j ++;
i = j - 1;
}
cnt ++;
}
}
cout << sum << ' ' << cnt;
return 0;
}
写的好长又好详细
hh,一般一般~
我的就写的挺短的啊😂