首页 > 代码库 > 【同一直线最多点】 poj 1118+2606+2780

【同一直线最多点】 poj 1118+2606+2780

poj 1118

#include<iostream>using namespace std;#define N 700struct point {int x,y;} pnt[N];int main(){    int n,i,j,k,max,cnt;    while(scanf("%d",&n)&&n)    {        for(i=0;i<n;i++)        scanf("%d%d",&pnt[i].x,&pnt[i].y);        max=0;        for(i=0;i<n;i++)        for(j=i+1;j<n;j++)        {            cnt=0;            for(k=j+1;k<n;k++)            {                if(k==i||k==j) continue;                int left=(pnt[i].x-pnt[k].x)*(pnt[j].y-pnt[k].y);                int right=(pnt[j].x-pnt[k].x)*(pnt[i].y-pnt[k].y);                if(left==right) cnt++;            }            max=max>cnt? max:cnt;        }         printf("%d\n",max+2);    }    return 0;}

 

 

 

poj 2606

#include <iostream>#include <cstdio>#include <memory.h>using namespace std;const int maxn=202;struct point{    int x;    int y;} pnt[maxn];int main(){    //freopen("in.txt","r",stdin);    int n,max,cnt;    while(cin >> n)    {        memset(pnt,0,sizeof(pnt));        for(int i=0;i<n;i++)        {            scanf("%d%d",&pnt[i].x,&pnt[i].y);        }        max=0;        for(int i=0;i<n;i++)        {            for(int j=i+1;j<n;j++)            {                cnt=0;                for(int k=j+1;k<n;k++)                {                    if(k==i || k==j)continue;                    int left=(pnt[i].x-pnt[k].x)*(pnt[j].y-pnt[k].y);                    int right=(pnt[j].x-pnt[k].x)*(pnt[i].y-pnt[k].y);                    if(left==right)cnt++;                }                 if(cnt>max)max=cnt;            }        }        cout << max+2 << endl;    }    return 0;}  

 

 

 

poj 2780

此题数据量比较大,同时虽然给的是3000ms,用n3算法也会超时,时间卡的紧,故一定要用n2lgn算法:

#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>using namespace std;const int maxn = 1002;const double eps = 1e-6;struct point{    int x,y;}node[maxn];double k[maxn];int n;bool equal(double x,double y){    if(abs(x-y) <= eps)    {        return true;    }    return false;}int max(int a,int b){    return a > b ? a : b;}void read(){    for(int i=0;i<n;i++)    {        scanf("%d %d",&node[i].x,&node[i].y);    }    return;}void solve(){    int ans = 0;    for(int i=0;i<n-1;i++)    {        int top = 0;        int tmp = 0;        for(int j=i+1;j<n;j++)        {            if(node[i].x == node[j].x)            {                tmp++;            }            else            {                k[top++] = (double)(node[j].y - node[i].y) / (node[j].x - node[i].x);            }        }        sort(k,k+top);        int cnt = 1;        for(int j=0;j<top;j++)        {            if(j < top-1 && equal(k[j],k[j+1]))            {                cnt++;            }            else            {                tmp = max(tmp , cnt);                cnt = 1;            }        }        ans = max(ans , tmp);    }    printf("%d\n",ans+1);    return;}int main(){    while(~scanf("%d",&n))    {        read();        solve();    }    return 0;}

 

 

注意对于每个点,都要求出当前对于此点的无斜率情况和最大斜率的数目的max

之后枚举每个点的上述max

之前wa了无数次,承蒙九龙大神给了一个平行四边形的测试数据才豁然开朗,同时当时对与斜率不存在的情况也没有依点而分析,造成错误在所难免,下附原来的wrong answer 代码:

#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <memory.h>using namespace std;const int maxn=1002;double s[500000+500];struct location_{    int x;    int y;}l[maxn];double slope(int m,int n){    double ans=(double)(l[m].y-l[n].y)/(double)(l[m].x-l[n].x);    return ans;}int main(){    //freopen("in.txt","r",stdin);    int n;    while(cin >> n)    {        memset(l,0,sizeof(l));        memset(s,0.0,sizeof(s));        int k=-1;        int slo_cnt=0;        for(int i=1;i<=n;i++)        {            scanf("%d%d",&l[i].x,&l[i].y);        }        for(int i=1;i<=n-1;i++)        {            for(int j=i+1;j<=n;j++)            {                if((l[i].x!=l[j].x))                {                    k++;                    s[k]=slope(i,j);                }                else                slo_cnt++;            }        }        for(int i=2;i<=10000;i++)        {            if(i*(i-1)/2==slo_cnt)            {                slo_cnt=i;                break;            }        }//        cout << slo_cnt << ">>"<< endl;//        for(int i=0;i<=k-1;i++)//        {//            cout << i << ‘ ‘ <<s[i] << endl;//        }        sort(s,s+k);//        for(int i=0;i<=k-1;i++)//        {//            cout << i << ‘ ‘ <<s[i] << endl;//        }        int cnt=0;        int max=0;        for(int i=1;i<=k-1;i++)        {            if(fabs(s[i]-s[i-1])<=0.00000001)            {                cnt++;                if(max<cnt)max=cnt;            }            else cnt=0;        }        max++;//        cout << "dsdsdsds"<< "   " <<max << endl;        for(int i=2;i<=10000;i++)        {            if(i*(i-1)/2==max)            {                max=i;                break;            }        }//        cout  << max<<"   max  " << endl;//        cout << slo_cnt << " slo_cnt "<<endl;        if(slo_cnt>max)max=slo_cnt;        cout << max << endl;    }    return 0;}

 

【同一直线最多点】 poj 1118+2606+2780