• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        
			
			


			
            
				
					
	
            
		
            
			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
             8int n,i,j,start,sum,count,pos[max][2];
             9double x[3],y[3];
            10
            11struct node
            12{
            13    int px,py;
            14    int next;
            15}            hash[len];
            16
            17void 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}
            35int 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}
            45void 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}
            53int 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
            83
            

              Code2:

              1            #include<stdio.h>
              2#include<stdlib.h>
              3#include<math.h>
              4#include<string.h>
              5#define max 2005
              6
              7int n,i,j,start,sum,count;
              8double x[3],y[3];
              9
             10struct node
             11{
             12    int px,py;
             13}            pos[max];
             14
             15int 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
             23int 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
             36int 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
             55
             56
             57void 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
             76int 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 閱讀(653) 評論(1)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    


            

            評論
            
	
	
			
            
				# re: pku 2002
					
						2009-08-20 20:48
					
				ning
			
            
			
            
				2分法的那個bsearch函數不能用么？  回復  更多評論
				  
			
            
		

            




            






            

				
				

			
            
			
            
				
					
            
	
            
		
            <2010年2月>
            
	
            日一二三四五六
            31123456
            78910111213
            14151617181920
            21222324252627
            28123456
            78910111213
            

            

					

            導航
            

					

            統計
            
	
					
					

            常用鏈接
            


            留言簿(8)
            


		
            隨筆檔案(78)
            
		
				
			
	



            搜索
            



            積分與排名
            



            最新評論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評論排行榜
            


				
			
            
			
			
			
			
			 

	
    
    







            
	   
	



AV无码久久久久不卡蜜桃|
国产香蕉久久精品综合网|
亚洲综合精品香蕉久久网|
久久99精品久久久久久久久久|
无遮挡粉嫩小泬久久久久久久|
亚洲一区二区三区日本久久九|
99精品伊人久久久大香线蕉|
亚洲精品第一综合99久久|
久久精品国产亚洲av水果派
|
亚洲中文字幕久久精品无码APP
|
久久久久国产一级毛片高清板|
亚洲va久久久久|
久久精品成人免费看|
久久天天躁狠狠躁夜夜avapp|
青青青青久久精品国产h|
亚洲国产小视频精品久久久三级|
久久精品国产半推半就|
精品多毛少妇人妻AV免费久久|
久久综合九色综合欧美狠狠|
久久婷婷五月综合成人D啪|
一本色道久久88加勒比—综合|
久久久久se色偷偷亚洲精品av|
久久国产美女免费观看精品
|
亚洲精品美女久久久久99|
国内精品久久久久久久影视麻豆|
麻豆AV一区二区三区久久|
思思久久99热只有频精品66|
久久久久人妻一区精品果冻|
久久国产乱子伦精品免费强|
无码国内精品久久人妻蜜桃|
久久久久久久波多野结衣高潮|
久久这里有精品视频|
九九久久精品国产|
久久精品国产色蜜蜜麻豆
|
久久久人妻精品无码一区|
伊人色综合久久天天|
亚洲国产成人久久综合碰碰动漫3d
|
97精品伊人久久久大香线蕉|
漂亮人妻被中出中文字幕久久|
香蕉aa三级久久毛片|
久久受www免费人成_看片中文|