蜜桃久久精品乱码一区二区,久久亚洲精品欧美,久久精品中文字幕一区

江蘇大學(xué)

pku 3668 Game of Lines hash

題意：
給出一些點(diǎn)，求出由這些點(diǎn)可以構(gòu)成多少斜率不同的線段。
解法：
O（N²）枚舉直線，然后hash記錄斜率（要特別考慮斜率不存在的情況），注意浮點(diǎn)數(shù)的比較精度控制在1e-8或者用pair來(lái)通分比較。。
代碼：

1

# include <iostream>
2

# include <cmath>
3

using namespace std;
4

# include <set>
5

struct cmp
6

{
7

bool operator()(const double a,const double b) const
8

{
9

return fabs(a-b)>1e-8&&a<b;
10

}
11

};
12

set<double,cmp> refer;
13

bool sp=0;
14

int data[201][2];
15

int 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

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


相關(guān)文章: pku3908 并查集的一點(diǎn)小變通 pku 3943 Digits on the Floor 并查集的活用（重點(diǎn)）+數(shù)字識(shí)別 2010 天津賽區(qū)G hdu 3726 splay 2010 ICPC天津賽區(qū) J hdu 3727 劃分樹(shù)的理解 pku 3225 區(qū)間我對(duì)線段樹(shù)延遲標(biāo)記的一些理解 pku1916 Rat Attack 動(dòng)態(tài)統(tǒng)計(jì)之經(jīng)典好題 pku3168 Barn Expansion 排序+區(qū)間重疊判斷 pku1944 Fiber Communications 圖論好題！總體上的觀察，算法不難 pku1894-1903 Northeastern Europe 2003 解題報(bào)告 pku2902 Intercepting Missiles 線段樹(shù)+離散化+二分圖匹配，注意C++短路

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理