(Relax ST1.13)POJ 2780 Linearity(给出若干个点,求最多有多少个点共线,不能使用n^3算法)

  • 阿里云国际版折扣https://www.yundadi.com

  • 阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6



    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    
    
    using namespace std;
    
    const int maxn = 1010;
    const int inf = INT_MIN;
    struct Point{
    	int x;
    	int y;
    
    	bool operator<(const Point& b)const{//排序规则这里怎么定义都无所谓,但是一定要定义。。。
    		if(x == b.x){
    			return y < b.y;
    		}
    
    		return x < b.x;
    	}
    }p[maxn];
    
    double cal(const Point& a,const Point& b){
    	if(b.x == a.x){
    		return inf;
    	}
    
    	return (b.y - a.y)*1.0/(b.x - a.x);
    }
    
    int main(){
    	int n;
    	while(scanf("%d",&n)!=EOF){
    		int maxm = -10;
    
    		double xielv[maxn*2];
    
    		int i;
    		for(i = 0 ; i < n ; ++i){
    			scanf("%d%d",&p[i].x,&p[i].y);
    		}
    
    		sort(p,p+n);
    		int j;
    		for(i = 0 ; i < n-1 ; ++i){
    			int index = 0;
    			for(j = i+1 ; j < n ; ++j){
    				xielv[index++] = cal(p[i],p[j]);
    			}
    
    			sort(xielv,xielv+index);//对斜率进行排序....
    
    
                /**
                 * 将斜率数组排序以后,这时候可能就会出现这么一种情况,
                 * 前后可能有好几个斜率是一样的...
                 * 以下就是数这样的斜率线每段有多少个...
                 */
    			for(j = 0 ; j < index ; ++j){
    				int count = 0;
    				while(fabs(xielv[j] - xielv[j+1]) == 0){
    					count++;
    					j++;
    				}
    
    				maxm = (maxm>count)?maxm:count;
    			}
    
    
    		}
    
    //		printf("%d\n",maxm+2);
    		cout<<maxm+2<<endl;
    	}
    
    	return 0;
    }



  • 阿里云国际版折扣https://www.yundadi.com

  • 阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6