首页 > 代码库 > 轰炸——运用直线方程,可能也算是平面计算几何

轰炸——运用直线方程,可能也算是平面计算几何

  用直线的标准方程推导一下,再枚举各点成为原点,可以快速判断某点是否在直线上。

技术分享
 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 }
Method_01

  洛谷 907ms

轰炸——运用直线方程,可能也算是平面计算几何