首页 > 代码库 > 轰炸——运用直线方程,可能也算是平面计算几何
轰炸——运用直线方程,可能也算是平面计算几何
用直线的标准方程推导一下,再枚举各点成为原点,可以快速判断某点是否在直线上。
1 #include<cstdio> 2 struct point{int x,y;}p[710]; 3 int n,cnt,ans; 4 int main(){ 5 scanf("%d",&n); 6 for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y); 7 ans=0; 8 for(int i=1;i<n;i++) 9 for(int j=i+1;j<=n;j++){10 int dx,dy,t;11 cnt=0;12 13 dx=p[j].x-p[i].x;14 dy=p[j].y-p[i].y;15 t=dx*p[i].y-dy*p[i].x;16 17 for(int k=1;k<=n;k++)cnt+=(dy*p[k].x-dx*p[k].y+t==0);18 19 if(ans<cnt)ans=cnt;20 }21 printf("%d\n",ans);22 return 0;23 }
洛谷 907ms
轰炸——运用直线方程,可能也算是平面计算几何
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。