您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

有关斜率的数学题?

转自自家学校的OJ网站

题目描述:

Description

 

cdwcgt成为了风纪班的成员!

风纪班的主要任务为维持治安、巡逻、注意可疑人物、仲裁吵架、追查违法药品,所涉及范围广大,偶尔会有较危险的工作。

职能与警方有重叠,因此经常与警察合作办案。

上任的第一天,cdwcgt就遇到了吸血鬼暴动。

在这个危急的时候,cdwcgt拿出了她的海德洛格拉迪尔特·改(其实就是把水枪,我们默认它是把机关枪),激光枪可以在这个时候同时从不同方向射出激光,激光会将这个直线上的人全部丧失战斗力。

问题很简单,一道激光最多能使多少人丧失战斗力。

Input

 

第一行一个数T,表示犯人的数量;
接下来T行,每行两个整数x,y,表示犯人的位置坐标。

Output

 

一道激光最多能使多少人丧失战斗力。

Sample Input 1

6
1 3
2 2
3 4
3 3
4 4
5 5

Sample Output 1

4

Hint

样例解释 : 打2,4,5,62, 4, 5, 62,4,5,6

 1<=T<=2000

1<=X,Y<=10^4

没有两个犯人的横、纵坐标相同。

第一遍看到这道题时,我的思路是用两个数组分别储存这些坐标x,y的值,通过对某一条纵线或横线或一条平分平面直角坐标系的线(我是初一,不太会描述请见谅)所穿过的点数进行排序,输出最大值骗一骗分的,可是我提交后发现“稻花香里说丰年,听取RE声一片”,我又想了想:数据怎么又这么恶心,骗不了分了~~~~(>_<)~~~~呜呜呜

第一次的代码:

#include<bits/stdc++.h>
using namespace std;
struct zb{
	int x;
	int y;
}z[10001];
int maxx(int l,int ll,int lll){
	int l1[3]={l,ll,lll};
	sort(l1,l1+2+1);
	return l1[2];
}
long long a[10001]={0},b[10001]={0},m=0,t,tj,m1,ans1=0;
int main(){
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>z[i].x>>z[i].y;
		if(z[i].x==z[i].y)
			tj++;
	}
	for(int i=1;i<=t;i++){
		a[z[i].x]++;
		b[z[i].y]++;
	}
	for(int i=1;i<=10000;i++){
		if(a[i]>m){
			m=a[i];
		}
	}
	for(int i=1;i<=10000;i++){
		if(b[i]>m1){
			m1=b[i];
		}
	}
	cout<<maxx(m1,m,tj);
	return 0;
}//跟个傻逼似的

然后,我就开始了我的找题解之路找思路之路,直到看到这篇文章快去看,我恍然大悟,我突然意识到我之前并没考虑到斜率有小于0的可能性,于是发现了这玩意:

map<pair<int,int> int>a;

STL里的好东西,将map和pair结合起来就可以让pair当下标,map来储存的效果,也就彻底解决了负数的情况:

AC伪代码:

 

for(int i=0;i<n;++i){
		map<pair<int, int>, int> a;
		int cnt=0,pcnt=0;
		for(int j=i+...;j<...;++j){
			if(m[i].x...m[j].x&&m[i].y...m[j].y){
				pcnt...;
			}
			else{
				int X=m[i]....-m[j]....;
				int Y=m[i]....-m[j]....;
				int g=...(X,Y);
				X/=...;
				Y/=...;
				int temp=++a[make_pair(X,Y)];
				cnt=max(...,temp);
			}
		}
		int kk=cnt+...;
		ma=max(...,kk+...);
	}

注意:斜率由于double的精度问题最好用分数储存,这也正是我们开二维map的原因,分数要记得约分!!!

                                                                                 ————byebye


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进