首页 > 代码库 > 【同一直线最多点】 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。