7-2 Finnish wooden chess structure Sorting

7-2 Finnish wood chess
fraction 25
author DAI, Longao
Company Hangzhou Baiteng Education Technology Co., Ltd
WX20200212-152528.png

Finnish wood chess （Mölkky, Also known as Finnish wooden column ） It's a sport from Finland . Zhe zhe transformed this sport into a cyberpunk single version , Now there are... On the court at the beginning N A small wooden chess with roots （ It is marked with a non negative integer ）, Zhe zhe throws a big wooden chess to knock down these small wooden chess to get points . The score rules are as follows ：

If you just knock down 1 Root wood chess , You get the score on the wooden chess .
If you knock down 2 Wooden chess with roots or more , You have to knock down the score of the number of pieces .（ For example, knock down 5 root , Then we get 5 branch .）
Zhe Zhe is standing on (0,0) light , There are several small wooden chess pieces around (X
i
​
,Y
i
​
), Coordinates are integers . Each time zhe zhe can throw a big wooden chess in one direction , Big wooden chess will knock down the nearest to zhe Zhe in this direction k A small wooden chess . Zhe Zhe's game level is very high , So this k Free to control .

How many points can zhe zhe get at most , At least how many times you need to throw a big wooden chess when you get the most points ？

The rules are quite different from the real rules , When you really play, please follow the rules of the international morky organization

Input format :
The first line of input is a positive integer N (1 ≤ N ≤ 10
5
), It means there was... At the beginning of the game N A wooden chess .

Next N That's ok , Each row 3 It's an integer X
i
​
,Y
i
​
,P
i
​
, It means that the wooden chess is placed in (X
i
​
,Y
i
​
), The score on wooden chess is P
i
​
. The coordinates are 32 Bit integer range , The score is less than or equal to 1000 The positive integer .

Guarantee (0,0) There is no wooden chess , There is no wooden chess overlapping .

Output format :
Output two numbers in one line , Indicates the maximum score and the minimum number of times it takes to throw a big wooden chess to get the maximum score .

sample input :
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
sample output :
1022 9

Can't write ：17 branch

Guess can be sorted by structure , Of the same slope w=1 All points are counted once , But when I met with the wrong person 1 After point , The tag needs to be reset
Just use map There is no way to judge in order

#include<bits/stdc++.h> 
 
using namespace std;
int ans,cnt;
map<double,bool> st1,st2;

bool x1,x2;

int main()
{
    
	int n;cin>>n;
	while(n--)
	{
    
		//int x,y;
		double x,y;
		int w;cin>>x>>y>>w;
		
		if(w==1)
		{
    
			double k=y*1.0/x;
			if(x)
			
			if(y>0){
    
				if(st1[k]==false){
    
					st1[k]=true;
					cnt++;
				}
			}else if(y==0){
    
				if(x>0&&x1==false){
    
					x1=true;
					cnt++;
				}
				if(x<0&&x2==false){
    
					x2=true;
					cnt++;
				}
			}else {
    
				if(st2[k]==false){
    
					st2[k]=true;
					cnt++;
				}
			}
			
		}
		else cnt++;
		ans+=w;
	} 
	cout<<ans<<" "<<cnt;
	return 0;
}

#include<bits/stdc++.h> 
 
using namespace std;

int ans,cnt;
map<double,bool> st1,st2;
int idx;
struct node
{
    
	int x,y;
	double k;
	int t=0;
}ns[100005];
int gcd(int a,int b)
{
    
	return b==0?a:gcd(b,a%b);
}

bool cmp(node a,node b)
{
    
	if(a.t!=b.t)return a.t<b.t;
	return a.k<b.k;
}
bool x1,x2;

int main()
{
    
	
	int n;cin>>n;
	while(n--)
	{
    
		int x,y;
		//double x,y;
		int w;cin>>x>>y>>w;
		
		if(w==1)
		{
    
			double k=y*1.0/x;
			
			int d=gcd(x,y);
			x/=d;
			y/=d;
			if(y>0)
			{
    
				ns[idx].x=x;
				ns[idx].y=y;
				ns[idx].k=k;
				ns[idx++].t=1;
			}else if(y<0)
			{
    
				ns[idx].x=x;
				ns[idx].y=y;
				ns[idx++].k=k;
			}else if(y==0)
			{
    
				if(x>0&&x1==false)
				{
    
					cnt++;
					x1=true;
				}
				else if(x<0&&x2==false)
				{
    
					cnt++;
					x2=true;
				}
			}
			
		}
		else cnt++;
		ans+=w;
	} 
	for(int i=0;i<idx;++i)
	{
    
		if(i==0){
    
            cnt++;
            continue;
        }
		if(ns[i-1].t==ns[i].t&&(ns[i-1].x!=ns[i].x||ns[i-1].y!=ns[i].y))
		{
    
			cnt++;
		}else if(ns[i-1].t!=ns[i].t){
    
			cnt++;
		}
	}
	cout<<ans<<" "<<cnt;
	return 0;
}