pku 3668 Game of Lines hash

题意：
给出一些点，求出由这些点可以构成多少斜率不同的线段。
解法：
O（N2）枚举直线，然后hash记录斜率（要特别考虑斜率不存在的情况），注意浮点数的比较精度控制在1e-8或者用pair来通分比较。。
代码：

 1# include <iostream>
 2# include <cmath>
 3using namespace std;
 4# include <set>
 5struct cmp
 6{
 7   bool operator()(const double a,const double b) const
 8   {
 9      return fabs(a-b)>1e-8&&a<b;
10   }
11}; 
12set<double,cmp> refer;
13bool sp=0;
14int data[201][2];
15int main()
16{
17   int n;
18   cin>>n;
19   for(int i=0;i<n;i++)
20   {
21     cin>>data[i][0]>>data[i][1];
22     for(int j=0;j<i;j++)
23       if(data[j][0]==data[i][0])
24         sp=1;
25       else
26          refer.insert((data[j][1]-data[i][1])/(double)(data[j][0]-data[i][0]));
27   }
28   cout<<refer.size()+sp<<endl;
29  // system("pause");
30   return 0;
31}
32

posted on 2010-12-05 01:26 yzhw 阅读(153) 评论(0)  编辑 收藏 引用 所属分类: data struct 、geometry&phycise


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年12月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜