久久精品人妻一区二区三区,国产AV影片久久久久久,婷婷久久综合九色综合98

pku 2002

2009年7月18日星期六

題目鏈接：PKU 2002 Squares

分類：哈希

題目分析與算法原型
         其實(shí)該題和1971很像（還有3432題除了輸入的點(diǎn)的范圍其他的基本和這題一模一樣）區(qū)別在于這題是統(tǒng)計(jì)正方形個(gè)數(shù)，而那題是統(tǒng)計(jì)平行四邊形個(gè)數(shù)，個(gè)人感覺這題稍微復(fù)雜一些，因?yàn)檎叫螌儆谄叫兴倪呅危矣媚穷}的思路，將那題的代碼改了一下，即在平行四邊形的基礎(chǔ)上判斷是否是正方形，結(jié)果TLE了，只能另找方法了。

算法1：其實(shí)可以發(fā)現(xiàn)一點(diǎn)，就是如果給你一個(gè)正方形的兩個(gè)對(duì)角線點(diǎn)的坐標(biāo)，則根據(jù)正方形的特點(diǎn)，一定可以算出另外的兩點(diǎn)的坐標(biāo)，利用這一點(diǎn)，這道題目基本就可以hash了，具體做法是，先將讀入的n個(gè)點(diǎn)的坐標(biāo)按照其x坐標(biāo)作為關(guān)鍵值進(jìn)行hash,然后像1971一樣枚舉每?jī)蓚€(gè)不同的點(diǎn)，將他們作為某個(gè)正方形的對(duì)角線，算出兩外的兩個(gè)點(diǎn)，然后對(duì)于新算出的兩個(gè)點(diǎn)的x坐標(biāo)進(jìn)行hash查找，對(duì)于x相同的點(diǎn)，判斷y是否也相同，若相同，則繼續(xù)hash另一個(gè)點(diǎn)的坐標(biāo)，若兩次都能找到則正方形個(gè)數(shù)加1。在哈希判斷時(shí)若找到相同的則直接退出本次查找，否則一直查找到鏈表的末尾，表示沒有以該兩點(diǎn)作為對(duì)角線的正方形。

算法2：這道題目還可以不用哈希，直接用二分來查找，同算法一，也是先枚舉每?jī)蓚€(gè)點(diǎn)，根據(jù)公式算出另外的兩個(gè)點(diǎn)，不過，直接用二分來查找這兩個(gè)點(diǎn)是否存在，當(dāng)然了，事先需要對(duì)輸入的坐標(biāo)排個(gè)序，先按x坐標(biāo)從小到大排序，相同的x的點(diǎn)以y坐標(biāo)從小到大排序，二分檢測(cè)時(shí)候，先找到與當(dāng)前被檢索的點(diǎn)的x坐標(biāo)相同的所有點(diǎn)的下標(biāo)范圍，然后再次在這個(gè)范圍里面再次二分查找是否存在與其y坐標(biāo)相同的點(diǎn).........
        需要注意的是這種方法，對(duì)于同一個(gè)正方形來說，因?yàn)榕c兩條對(duì)角線，所以會(huì)算了兩次，所以最后輸出的時(shí)候需要除以2，呵呵

Code1:

1

#include<stdio.h>
2

#include<math.h>
3

#include<string.h>
4

#define max 1005
5

#define pianyi 20005
6

#define prime 39997
7

#define len 50000
8

int n,i,j,start,sum,count,pos[max][2];
9

double x[3],y[3];
10

struct node
12

{
13

int px,py;
14

int next;
15

}hash[len];
16

void cal(int a,int b)
18

{
19

double x0=(double)(pos[a][0]+pos[b][0])/2,y0=(double)(pos[a][1]+pos[b][1])/2;
20

if((pos[b][1]-pos[a][1])*(pos[b][0]-pos[a][0])>0)
21

{
22

x[1]=x0-fabs(pos[b][1]-pos[a][1])/2;
23

x[2]=x0+fabs(pos[b][1]-pos[a][1])/2;
24

y[1]=y0+fabs(pos[b][0]-pos[a][0])/2;
25

y[2]=y0-fabs(pos[b][0]-pos[a][0])/2;
26

}
27

else
28

{
29

x[1]=x0-fabs(pos[b][1]-pos[a][1])/2;
30

x[2]=x0+fabs(pos[b][1]-pos[a][1])/2;
31

y[1]=y0-fabs(pos[b][0]-pos[a][0])/2;
32

y[2]=y0+fabs(pos[b][0]-pos[a][0])/2;
33

}
34

}
35

int Hash2(int x,int y)
36

{
37

int now=x%prime;
38

while(hash[now].next!=-1)
39

{
40

if(hash[hash[now].next].py==y)return 1;
41

now=hash[now].next;
42

}
43

return 0;
44

}
45

void Hash(int k)
46

{
47

int now=k%prime;
48

while(hash[now].next!=-1)now=hash[now].next;
49

hash[start].next=-1;
50

hash[now].next=start;
51

start++;
52

}
53

int main()
54

{
55

while(scanf("%d",&n)!=EOF&&n)
56

{
57

start=prime+10;
58

memset(hash,-1,sizeof(hash));
59

for(i=0;i<n;i++)
60

{
61

scanf("%d%d",&pos[i][0],&pos[i][1]);
62

hash[start].px=pos[i][0];
63

hash[start].py=pos[i][1];
64

Hash(pos[i][0]+pianyi);
65

}
66

count=0;
67

for(i=0;i<n-1;i++)
68

for(j=i+1;j<n;j++)
69

{
70

int res1,res2;
71

cal(i,j);
72

int t1=(int)x[1],t2=(int)x[2],t3=(int)y[1],t4=(int)y[2];
73

if(t1!=x[1]||t2!=x[2]||t3!=y[1]||t4!=y[2])continue;
74

res1=Hash2((int)x[1]+pianyi,(int)y[1]);
75

res2=Hash2((int)x[2]+pianyi,(int)y[2]);
76

if(res1&&res2)count++;
77

}
78

printf("%d\n",count/2);
79

}
80

return 0;
81

}
82

Code2:

1

#include<stdio.h>
2

#include<stdlib.h>
3

#include<math.h>
4

#include<string.h>
5

#define max 2005
6

int n,i,j,start,sum,count;
8

double x[3],y[3];
9

struct node
11

{
12

int px,py;
13

}pos[max];
14

int cmp(const void *a,const void *b)
16

{
17

struct node *c=(node *)a;
18

struct node *d=(node *)b;
19

if(c->px!=d->px)return c->px-d->px;
20

else return c->py-d->py;
21

}
22

int search2(int low,int high,int y)
24

{
25

int mid;
26

while(low<=high&&low>=0&&high<n)
27

{
28

mid=(low+high)/2;
29

if(y<pos[mid].py)high=mid-1;
30

else if(y>pos[mid].py)low=mid+1;
31

else return 1;
32

}
33

return 0;
34

}
35

int search(int low,int high,int x,int y)
37

{
38

int mid;
39

while(low<=high&&low>=0&&high<n)
40

{
41

mid=(low+high)/2;
42

if(x<pos[mid].px)high=mid-1;
43

else if(x>pos[mid].px)low=mid+1;
44

else
45

{
46

int start=mid,end=mid;
47

while(pos[start].px==x&&start>=0)start--;
48

while(pos[end].px==x&&end<n)end++;
49

return search2(start+1,end-1,y);
50

}
51

}
52

return 0;
53

}
54

void cal(int a,int b)
58

{
59

double x0=(double)(pos[a].px+pos[b].px)/2,y0=(double)(pos[a].py+pos[b].py)/2;
60

if((pos[b].py-pos[a].py)*(pos[b].px-pos[a].px)>0)
61

{
62

x[1]=x0-fabs(pos[b].py-pos[a].py)/2;
63

x[2]=x0+fabs(pos[b].py-pos[a].py)/2;
64

y[1]=y0+fabs(pos[b].px-pos[a].px)/2;
65

y[2]=y0-fabs(pos[b].px-pos[a].px)/2;
66

}
67

else
68

{
69

x[1]=x0-fabs(pos[b].py-pos[a].py)/2;
70

x[2]=x0+fabs(pos[b].py-pos[a].py)/2;
71

y[1]=y0-fabs(pos[b].px-pos[a].px)/2;
72

y[2]=y0+fabs(pos[b].px-pos[a].px)/2;
73

}
74

}
75

int main()
77

{
78

while(scanf("%d",&n)!=EOF&&n)
79

{
80

for(i=0;i<n;i++)scanf("%d%d",&pos[i].px,&pos[i].py);
81

qsort(pos,n,sizeof(pos[0]),cmp);
82

count=0;
83

for(i=0;i<n-1;i++)
84

for(j=i+1;j<n;j++)
85

{
86

int res1,res2;
87

cal(i,j);
88

int t1=(int)x[1],t2=(int)x[2],t3=(int)y[1],t4=(int)y[2];
89

if(t1!=x[1]||t2!=x[2]||t3!=y[1]||t4!=y[2])continue;
90

res1=search(0,n-1,x[1],y[1]);
91

if(!res1)continue;
92

res2=search(0,n-1,x[2],y[2]);
93

if(res1&&res2)count++;
94

}
95

printf("%d\n",count/2);
96

}
97

return 0;
98

}
99

100

posted on 2009-07-18 23:45 蝸牛也Coding 閱讀(644) 評(píng)論(1) 編輯收藏引用

評(píng)論

# re: pku 2002 2009-08-20 20:48 ning

2分法的那個(gè)bsearch函數(shù)不能用么？回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



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

# re: pku 2002 2009-08-20 20:48 ning

pku 2002

評(píng)論

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜