[牛客网 -leetcode在线编程 -01] max-points-on-a-line -穷举

题目及题目来源

链接：https://www.nowcoder.com/questionTerminal/bfc691e0100441cdb8ec153f32540be2

来源：牛客网

首页 > 试题广场 > max-points-on-a-line

[编程题]max-points-on-a-line

热度指数：67696 时间限制：1秒 空间限制：32768K

 算法知识视频讲解

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

题解及完整类

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 9;

int high=0; //++high mode

struct Point {

	int x;

    int y;

    Point() : x(0), y(0) {}

    Point(int a, int b) : x(a), y(b) {}

 };

 /*

 链接：https://www.nowcoder.com/questionTerminal/bfc691e0100441cdb8ec153f32540be2

来源：牛客网

 需要两重循环，第一重循环遍历起始点a，第二重循环遍历剩余点b。

    a和b如果不重合，就可以确定一条直线。

    对于每个点a，构建 斜率->点数 的map。

    (1)b与a重合，以a起始的所有直线点数+1 (用dup统一相加)

    (2)b与a不重合，a与b确定的直线点数+1

 */

class Solution {

public:

    int maxPoints(vector<Point> &points) {

        int size=points.size();

		if(size==0)return 0;

		else if(size==1)return 1;

		else if(size==2) return 2;

		int ret=0;

		for(int i=0;i<size;i++){ //遍历起点a 

			map<double,int>mp; //构建斜率->点数的map集合

			int vcent=0; //垂直的点

			int dub=0; //重合的点 

			for(int j=0;j<size;j++){ //枚举起点b

				if(i==j)continue;

				//确定x,y的差值: x1,x2

				double x1 = points[i].x-points[j].x;

				double y1 = points[i].y-points[j].y;

				//重合的情况

				if(x1==0&&y1==0){

					dub++;

					ret=max(ret,dub+1);

				} //垂直线上的情况

				else if(x1==0){

					vcent++;

					ret=max(ret,1+dub+vcent);

				}

					// 求出斜率,保存到map中

				else{

					double k=y1/x1;

					mp[k]++;

					ret=max(ret,1+dub+mp[k]);

				}

//				cout<<"i= "<<i<<" j="<<j<<" ret="<<ret;

//				printf(" dub=%d vent=%d\n",dub,vcent);

			}

			//	cout<<endl;

		}

		return ret;

    }

};

//void debug(vector<Point> points){  //输出重复的点的情况,并且最后输出去重的vector表

//		int len=points.size();

//

//    	map<int,int>mp;

//

//		for(int i=0;i<points.size();i++){

//			for(int j=points.size()-1;j>i;j--){

//				if(points[i].x==points[j].x&&points[i].y==points[j].y){

//					mp[i]++;

//					points.erase(points.begin()+j);

//					j=points.size();

//				}

//			}

//		}

//		map<int,int>::iterator it=mp.begin();

//		for(;it!=mp.end();it++){

//			cout<<it->first<<"******"<<it->second<<endl;

//		}

//		cout<<endl;

//}

int main(){

	int n;

	char arr[12][12];

	memset(arr,' ',sizeof(arr));

	while(1){

		cin>>n;

		vector<Point>p;

		int x,y;

		for(int i=0;i<n;i++){

			scanf("%d%d",&x,&y);

			p.push_back(Point(x,y));

	//		arr[x][y]='*';

		}

		debug(p);

		Solution s;

		cout<<s.maxPoints(p)<<endl;	

	}

//	cout<<"_____________________"<<endl;

//	for(int i=0;i<10;i++){

//		arr[i][11]='\0';

//		cout<<arr[i]<<endl;

//	}

//	cout<<"_____________________"<<endl;

	return 0;

}

简单测试数据



/*

	思路: 穷举,

	用例:

	9

	 84 250 0 0 1 0 0 -70 0 -70 1 -1 21 10 42 90 -42 -230

	 3

	 1 1 1 1 1 1

	4

	 1 1 1 1 1 1 2 3

	 5

	 1 1 1 1 1 1 2 3 2 3

	 6

	 1 1 1 1 1 1

	 2 3 2 3 4 67

	 1

	  0  0

用例:

[(84,250),(0,0),(1,0),(0,-70),(0,-70),(1,-1),(21,10),(42,90),(-42,-230)]

对应输出应该为:

6

你的输出为:

96 7 8 9 2 6 4 7 2 9 

*/

/*

	ctrl+E ,复制行

	ctrl+shift+A :整体缩进对齐

	ctrl+D: 删除当前行

*/

巴特西

[牛客网 -leetcode在线编程 -01] max-points-on-a-line -穷举

题目及题目来源

题解及完整类

简单测试数据

最新文章

热门文章

巴特西

[牛客网 -leetcode在线编程 -01] max-points-on-a-line -穷举

题目及题目来源

题解 及完整类

简单测试数据

最新文章

热门文章

题解及完整类