【计算几何】【斜率】bzoj1610 [Usaco2008 Feb]Line连线游戏

ゞ 浴缸里的玫瑰 2022-01-07 01:15 237阅读 0赞

枚举直线,计算斜率,排序,统计答案。

  1. #include<cstdio>
  2. #include<cmath>
  3. #include<algorithm>
  4. using namespace std;
  5. #define EPS 0.00000001
  6. #define INF 99999999999999999999.0
  7. #define N 201
  8. typedef double db;
  9. int n,m,sta,ans;
  10. db xs[N],ys[N],line[N*N];
  11. int main()
  12. {
  13. scanf("%d",&n);
  14. for(int i=1;i<=n;++i)
  15. scanf("%lf%lf",&xs[i],&ys[i]);
  16. for(int i=1;i<=n;++i)
  17. for(int j=i+1;j<=n;++j)
  18. line[++m]=(fabs(xs[i]-xs[j])<EPS?INF:(ys[i]-ys[j])/(xs[i]-xs[j]));
  19. sort(line+1,line+m+1);
  20. for(int i=1;i<=m;++i)
  21. if(i==1||fabs(line[i]-line[i-1])>EPS)
  22. ++ans;
  23. printf("%d\n",ans);
  24. return 0;
  25. }

转载于:https://www.cnblogs.com/autsky-jadek/p/4372906.html

发表评论

表情:
评论列表 (有 0 条评论,237人围观)

还没有评论,来说两句吧...

相关阅读

    相关 bzoj 2823(计算几何+最小覆盖圆)

    问题描述: 在野外训练中,为了确保每位参加集训的成员安全,实时的掌握和收集周边环境和队员信息非常重要,集训队采用 的方式是在训练所在地散布N个小型传感器来收集并传递信息,这

    相关 计算几何

    平面上有有条线段,判断这两条线段是否会相交。 【line.in】 0 0 1 1 0 1 1 0 【line.out】 1 判断线段相交可以用跨立实验+快速排斥