久久亚洲欧美国产精品,久久久精品波多野结衣,狠狠色婷婷久久综合频道日韩

pku 2002

2009年7月18日星期六

題目鏈接：PKU 2002 Squares

分類：哈希

題目分析與算法原型
         其實該題和1971很像（還有3432題除了輸入的點的范圍其他的基本和這題一模一樣）區別在于這題是統計正方形個數，而那題是統計平行四邊形個數，個人感覺這題稍微復雜一些，因為正方形屬于平行四邊形，我用那題的思路，將那題的代碼改了一下，即在平行四邊形的基礎上判斷是否是正方形，結果TLE了，只能另找方法了。

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

算法2：這道題目還可以不用哈希，直接用二分來查找，同算法一，也是先枚舉每兩個點，根據公式算出另外的兩個點，不過，直接用二分來查找這兩個點是否存在，當然了，事先需要對輸入的坐標排個序，先按x坐標從小到大排序，相同的x的點以y坐標從小到大排序，二分檢測時候，先找到與當前被檢索的點的x坐標相同的所有點的下標范圍，然后再次在這個范圍里面再次二分查找是否存在與其y坐標相同的點.........
        需要注意的是這種方法，對于同一個正方形來說，因為與兩條對角線，所以會算了兩次，所以最后輸出的時候需要除以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 閱讀(648) 評論(1) 編輯收藏引用

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

pku 2002

評論

導航

統計

常用鏈接

留言簿(8)

隨筆檔案(78)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理