《程序設(shè)計(jì)藝術(shù)與方法》課程實(shí)驗(yàn)報(bào)告.

1、程序設(shè)計(jì)藝術(shù)與方法課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱STL的熟悉與使用姓 名系院專業(yè)計(jì)算機(jī)與 信息學(xué)院班級計(jì)算機(jī)科 學(xué)與技術(shù) 122 班學(xué) 號2012211643實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成 績一、實(shí)驗(yàn)?zāi)康暮鸵?. (1)掌握C+中STL的容器類使用。(2)掌握C+中STL的算法類的使用。二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容Vector,list可當(dāng)作列表使用的數(shù)據(jù)結(jié)構(gòu)，它們都是動(dòng)態(tài)增長的。1.vector表7L段連續(xù)的內(nèi)存區(qū)域母個(gè)兀素被順序儲(chǔ)存在這段內(nèi)仔中。對vector的隨即訪問效率很高。但是在任意位置而不是在 vector末尾插入兀素則效率很低，因?yàn)樗枰汛迦胴Ｋ?的右邊的每個(gè)兀素都拷貝一遍。類似的刪除任一個(gè)而不是ve

2、ctor的最舟-個(gè)兀素效率低。2list表示非連續(xù)的內(nèi)存區(qū)域并通過一對指向首尾元素的指針雙向進(jìn)行遍歷在list的任意位置插入和刪除兀素的效率都很高，指針必須被賦值但不需要用拷貝兀素來實(shí)現(xiàn)移動(dòng)，另一方面它對隨機(jī)訪問的支持并不好訪問一個(gè)元素需要遍歷中間的元素，另外每個(gè)元素還有倆不能給個(gè)指針的額外空間開銷。3泛型算法讓編寫一般化并可重復(fù)使用的算法，其效率與指針對某特定數(shù)據(jù)類型而設(shè)計(jì)的算法相同。泛型即是指具有在多種數(shù)據(jù)類型上皆可操作的含義，與模板有些相似。STL巨大而且可以擴(kuò)充，它包含很多計(jì)算機(jī)基本算法和數(shù)據(jù)結(jié)構(gòu)，而且將算法與數(shù)據(jù)結(jié)構(gòu)完全分離，其中算法是泛型的，不與任何特定數(shù)據(jù)結(jié)構(gòu)或?qū)ο箢愋拖翟谝黄稹?/p>

3、三、實(shí)驗(yàn)項(xiàng)目摘要1.練習(xí)vector和list的使用。te義一個(gè)空的vector,兀素類型為int,生成10個(gè)隨機(jī)數(shù)插入到vector中，用迭代器遍歷vector并輸出其中的九素值。在 vector頭部插入一個(gè)隨機(jī)數(shù)，用迭代器遍歷vector并輸出其中的元素值。用泛型算法find查找某個(gè)隨機(jī)數(shù)，如果找到便輸出，否則將此數(shù)插入vector尾部。用泛型算法sort將vector排序，用迭代器遍歷 vector并輸出其中的元 素值。刪除vector尾部的兀素，用迭代器遍歷 vector并輸出其中的兀素值。將 vector清 空。定義一個(gè)list,并重復(fù)上述實(shí)驗(yàn)，并注意觀察結(jié)果2練習(xí)泛型算法的使用。t

4、e義一個(gè)vector,兀素類型為int,插入10個(gè)隨機(jī)數(shù)，使用sort按升字排序，輸出每個(gè)元素的值，再按降敘排序，輸出每個(gè)元素的值。練習(xí)用find查找元素。用min和max找出容器中的最小元素個(gè)最大元素，并輸出。四、實(shí)驗(yàn)結(jié)果與分析(源程序及相關(guān)說明)1.練習(xí)vector和list的使用：#include <iostream>#include <vector>#include<iomanip>#include<ctime>#include <algorithm>using namespace std;vector<int>

5、myV;bool sortup(int v1,int v2)return v1<v2;int main(int argc, char *argv口)srand(time(NULL);/隨機(jī)產(chǎn)生十個(gè)數(shù)for (int i=0;i<10;i+)myV.push_back(rand();sort(myV.begin(),myV.end(),sortup); 用 sort 排序升序vector<int>二iterato門t1;for (it1=myV .begin();it1!=myV .end();it1+)cout<v(*it1)v<setw(6); 打印數(shù)組c

6、out<<endl;int min=myV0;for (it1=myV .begin()+1;it1!=myV .end();it1+)if(*it1)<min)min=(*it1);cout<<"最小元素為"<<min<<endl;int max=myV0;for (it1=myV .begin();it1!=myV.end();it1+)if(*it1)>max)max=(*it1);cout<<"最大元素為"<<max<<endl;cout<<

7、;endl;int value=rand();it1=find(myV .begin(),myV.end(),value);if(*it1)=value)cout<<"找到了這個(gè)隨機(jī)數(shù)"<<endl ;elsecout<<"沒有找到這個(gè)隨機(jī)數(shù)"<<endl;myV.insert(myV.end(),value); /數(shù)組中沒有隨機(jī)數(shù)，插入尾部 cout<<”插入尾部的隨機(jī)數(shù)為"<<value<<endl;for (it1=myV .begin();it1!=my

8、V .end();it1+)cout<<(*it1)<<setw(6);cout<<"n"<<endl;/隨機(jī)在vector頭部插入一個(gè)隨機(jī)數(shù)int t=rand();/定義t;將一個(gè)隨機(jī)數(shù)賦給t,插入到數(shù)組頭部myV.insert(myV.begin(),t);cout<<"插入頭部的隨機(jī)數(shù)為"<<t<<endl;for (it1=myV .begin();it1!=myV .end();it1+)cout<<(*it1)<<setw(6);co

9、ut<<endl;/刪除尾部元素myV.pop_back ();for (it1=myV .begin();it1!=myV.end();it1+)cout<<(*it1)<<setw(6);cout<<endl;myV.clear();/清空數(shù)組if(myV .empty()cout << "It's empty!" << endl;system("PAUSE"); /press any key to continue. return 0;運(yùn)行截圖：7&78 115

10、89 13582 128? 13?081G925194212143421940小石左方 大元素為319431G2251942131L05售人頭部的隨機(jī)數(shù)為“好7t79 11S88 13&82 12997 12909 1G225 19421 21434 ?居姬 31940 14859 5486 7t7B 115S8 15582 L3897 139酮 162四 ±9421 21434 3150G 2±?40 Rt，* cnptyt青按任意錯(cuò)也續(xù).一2練習(xí)泛型算法的使用：#include<list>#include<iostream>/#inclu

11、ed<algorithm>using namespace std;typedef list<int> lin;int value=1,6,7,8,9; 定義一個(gè)數(shù)組 value 并賦值 void print(lin &l)int i;lin:iterator lit;/ 定義一個(gè)迭代器for(lit=l.begin();lit!=l.end();lit+)cout<<(*lit)<<" "/依次才丁印list中的元素 cout<<endl;bool sortsp(int v1,int v2)/定義一個(gè)升序排

12、序算法 return v1>v2;int main()lin lin2;lin2.push_front(3); /單獨(dú)逐個(gè)插入幾個(gè)數(shù)lin2.push_front(4);lin2.insert(lin2.begin(),value,value+5);cout<<"lin2內(nèi)的元素為："print(lin2);lin2.sort();/對鏈表11進(jìn)行從小到大排序cout<<"排序后的 1in2:"print(1in2);1in2.push_front(10);/在 list 頭部插入 10cout<<"在

13、list頭部插入10之后的結(jié)果："print(lin2);lin2.remove(6);cout<<"刪除一個(gè)數(shù)后的lin1:"print(lin2);system("PAUSE");press any key to contineu return 0;/List不允許對隨機(jī)數(shù)進(jìn)行操作運(yùn)行截圖：Wn2I -“口 ： 6。安全.克器下舞1' M i 匚rs oft Vi ual、tudioM y Proj百咆元索為,后的 lin2* 13 4 6 7 6 9睢1迤1:頭部插入1Z之后的結(jié)果；18 1 3 4 fc 7 8 9I

14、linlstB 13 4 7 8 9實(shí)驗(yàn)名稱搜索算法的實(shí)驗(yàn)姓 名黃星辰系院專業(yè)計(jì)算機(jī)與 信息學(xué)院班級計(jì)算機(jī)科 學(xué)與技術(shù)122 班學(xué)號2012211643實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成績一、實(shí)驗(yàn)?zāi)康暮鸵? .掌握寬度優(yōu)先搜索算法。2 .掌握深度優(yōu)先搜索算法。二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容1寬度優(yōu)先搜索算法：又稱廣度優(yōu)搜索。是最簡單的圖的算法的原形。其屬于一種盲搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以尋找結(jié)果。換句話說，它并不考慮結(jié)果的可能位址，徹底地搜索整張圖，直到找到結(jié)果為止。2深度優(yōu)先搜索算法：它的目的是要達(dá)到被搜索結(jié)構(gòu)的葉結(jié)點(diǎn)。在一個(gè)HTML文件中，當(dāng)一個(gè)超鏈被選擇后，被連接的 HTML文件將執(zhí)行深

15、度優(yōu)先搜索，即在搜索其余的超鏈走到不能再 深入為止，然后返回到某一個(gè)HTML文件，再繼續(xù)選擇該 HTML文件中的其他超鏈。當(dāng)不再有其他超鏈可選擇時(shí)，說明搜索已經(jīng)結(jié)束。三、實(shí)驗(yàn)項(xiàng)目摘要1 .將書上的走迷宮代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果，并注意體會(huì)搜索的思想。2 .八皇后問題：在一個(gè)國際象棋棋盤上放八個(gè)皇后，使得任何兩個(gè)皇后之間不相互攻擊，求出所有的布棋方法。上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。思考：將此題推廣到 N皇后的情況，檢驗(yàn)在 N比較大的情況下，比方說 N=16的時(shí) 候，你的程序能否快速的求出結(jié)果，如果不能，思考有什么方法能夠優(yōu)化算法。3騎士游歷問題：在國際棋盤上使一個(gè)騎士遍歷所有的格子一遍且僅一遍，對于任意給定

16、的頂點(diǎn)，輸出一條符合上述要求的路徑。4倒水問題：給定2個(gè)沒有刻度容器，對于任意給定的容積，求出如何只用兩個(gè)瓶裝出L升的水，如果可以，輸出步驟，如果不可以，請輸出 No Solution。四、實(shí)驗(yàn)結(jié)果與分析(源程序及相關(guān)說明)2,八皇后問題:#include <stdio.h>/*聲明常量N存儲(chǔ)行和列*/# define N 8# define NUM 8/*聲明全局變量，hNN控制盤格，HNN控制輸出，nN存儲(chǔ)每一步的# 縱坐標(biāo)，count用于計(jì)數(shù)。# /int hNN,nN,HNN;int count=0;/*聲明函數(shù)void tryit(int,int)嘗試符合條件的方法*/v

17、oid tryit(int,int);/*聲明函數(shù) void outputArray(intN)輸出數(shù)組*/void outputArray(intN);main()int x=0,y=0,i,j;/*初始化為零*/for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)h皿=0；tryit(x,y);printf("/其他的布局略n");printf("共有 d 種布局.n”,92);return(0);/*定義函數(shù)void tryit(int,int)嘗試符合條件的方法*/void tryit(int x,int y)int i,j

18、;if(count<=NUM)/*重復(fù)時(shí)跳出遞歸*/if(H00=1&&H14=1&&H27=1&&H35=1&&H42=1&&H56 =1&&H61=1&&H73=1)&&count!=1)elseif(x>=0&&x<=N-1&&y>=0&&y<=N-1&&hxy=0)/*對與皇后在同一行、歹h斜線上的點(diǎn)作出處理*/for(j=0;j<=7;j+)(if(hxj=0

19、)hxj=x+1;if(h皿y=0)hjy=x+i；if(x+j>=0&&x+j<=N-1&&y+j>=0&&y+j<=N-1&&hx+jy+j=0) hx+jy+j=x+1;if(x+j>=0&&x+j<=N-1&&y-j>=0&&y-j<=N-1&&hx+jy-j=0) hx+jy-j=x+1;if(x-j>=0&&x-j<=N-1&&y+j>=0&&

20、y+j<=N-1&&hx-jy+j=0)hx-jy+j=x+1;if(x-j>=0&&x-j<=N-1&&y-j>=0&&y-j<=N-1&&hx-jy-j=0) hx-jy-j=x+1;)/*對皇后處的點(diǎn)作出標(biāo)志*/hxy=-x-1;/*完成一種走法作出處理*/if(x=7)(/*轉(zhuǎn)換成輸出的格式*/for(i=0;i<=N-1;i+)(for(j=0;j<=N-1;j+)(if(hij<0)Hij=1;elseHij=0;)count=count+1;/*輸出前幾

21、種情況*/if(count<=NUM) printf("布局 dn",count);outputArray(H);/*對下一種走法，清楚前一次的影響*/ for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)if(hij=x|hij=-x|hij=-x-1)hij=0；/*遞歸，嘗試另一種方法*/ tryit(x-1,nx-1+1);/*未走完一次，繼續(xù)下一行*/elsenx=y;tryit(x+1,0)；else/*此路不通時(shí)，返回上一行，嘗試下一種方法 */if(y>7)/*清楚前一次影響*/for(i=0;i<=N-1;

22、i+)for(j=0;j<=N-1;j+)if(h皿=x|hij=-x)h皿=0；/*分情況遞歸*/if(x-1>=0)tryit(x-1,nx-1+1);elsetryit(0,0)；/*嘗試下一格*/elsetryit(x,y+1);/*定義函數(shù) void outputArray(intN)輸出數(shù)組*/ void outputArray(int hN)int i,j;for(i=0;i<=N-1;i+)for(j=0;j<=N-1;j+)printf("%d ",hij);printf("n");運(yùn)行截圖:一布局T-出爐自住1

23、中內(nèi)修 00080001 6008010a3 0 0 Q 0 1 Q 61003008 60010099布局260086091 03100009 RDB修01000009布局33 .騎士游歷問題：在國際棋盤上使一個(gè)騎士遍歷所有的格子一遍且僅一遍，對于任意給定的頂點(diǎn), 輸出一條符合上述要求的路徑。#include <stdio.h>int board88 = 0;int main(void) int startx, starty;int i, j；printf("輸入起始點(diǎn):");scanf("%d %d", &startx, &

24、;starty);if(travel(startx, starty) printf("游歷完成！ n");else printf("游歷失敗！ n");for(i = 0; i < 8; i+) for(j = 0； j < 8; j+) printf("%2d ", boardjputchar('n');return 0;int travel(int x, int y)int ktmove18 = -2, -1, 1,2, 2, 1, -1, -2; / 對應(yīng)騎士可走的八個(gè)方向int ktmove28 =

25、 1,2, 2, 1, -1, -2, -2, -1; / 測試下一步的出路int nexti8 = 0;int nextj8 = 0; / 記錄出路的個(gè)數(shù)int exists8 = 0;int i, j, k, m, l;int tmpi, tmpj;int count, min, tmp;i = x;j = y;boardij = 1;for(m = 2; m <= 64; m+) for(l = 0; l < 8; l+)existsl = 0;l = 0;/試探八個(gè)方向for(k = 0; k < 8; k+) tmpi = i + ktmove1k;tmpj = j

26、 + ktmove2k; /如果是邊界了，不可走if(tmpi < 0 | tmpj < 0 | tmpi > 7 | tmpj > 7)continue; /如果這個(gè)方向可走，記錄下來if(boardtmpitmpj = 0) nextil = tmpi;nextjl = tmpj; /可走的方向加一個(gè) l+;count = l; /如果可走的方向?yàn)?個(gè)，返回 if(count = 0) return 0;else if(count = 1) /只有一個(gè)可走的方向/所以直接是最少出路的方向min = 0; else /找出下一個(gè)位置的出路數(shù)for(l = 0; l &

27、lt; count; l+) for(k = 0; k < 8; k+) tmpi = nextil + ktmove1k;tmpj = nextjl + ktmove2k;if(tmpi < 0 | tmpj < 0 | tmpi > 7 | tmpj > 7) continue;if(boardtmpitmpj = 0) existsl+;tmp = exists0;min = 0; /從可走的方向中尋找最少出路的方向 for(l = 1; l < count; l+) if(existsl < tmp) tmp = existsl;min = l

28、;/走最少出路的方向i = nextimin;j = nextjmin;board皿=m;return 1;運(yùn)行截圖：1 162722318475626 232174£5741915 2825622148555824 353045606320529 14bl3449445?5436 31384164536y13 483350118435232 3712394251107Ppess an9 key to continue*川4 .倒水問題：#include"stdio.h"int main()int ca,cb,cc,x,y;while(scanf("%d

29、%d%d",&ca,&cb,&cc)!=EOF) if(cb=cc)printf("fill B'n");else if(ca=cc)printf("削 A'n");printf("pourA B'n"); elsex=y=0;if(ca<cc)while(1)if(y=0)y=cb;printf("fill B'n");if(y>ca-x)/如果b中的水大于a中的剩余容積，就把a(bǔ)灌滿y-=ca-x;x=ca;printf("p

30、our B A'n"); else/如果b中的水小于a中的剩余容積，那么把b中的水全加入a/x+=y;y=0;printf("pour B A'n");if(y=cc)/如果b中的水已經(jīng)和cc相等，那就結(jié)束break;if(ca=x)/如果a中的水滿了，就把a(bǔ)倒空x=0;printf("empty A'n");elsewhile(1)if(x=0)x=ca;printf("fill A'n");if(x>cb-y)/如果a中的水大于b中的剩余容積，就把b灌滿x-=cb-y;y=cb;pr

31、intf("pourA B'n"); else/如果a中的水小于b中的剩余容積，那么把a(bǔ)中的水全加入b/ y+=x；x=0;printf("pourA B'n");if(y=cc)/如果b中的水已經(jīng)和cc相等，那就結(jié)束break;if(y=cb)/如果b中的水滿了，就把b倒空y=0;printf("empty B'n");printf("successn");return 0;運(yùn)行截圖："斐全定r高器大帽MicFosnft Visual EtudioMProjectsypuD&am

32、p;bugijpu.eatewfc 7 5 fill A VDUF ft B fill A puur A B empty It jiour A B success 7 9 8 rm B pour* B A enpt A puur B 由 pll D pour B A enpt5 A pom? B 俞 ini d pour B A empty 妹 pour B A fill B I)Dur B A success實(shí)驗(yàn)名稱計(jì)算幾何算法的實(shí)現(xiàn)姓 名黃星辰系院專業(yè)計(jì)算機(jī)與 信息學(xué)院班級計(jì)算機(jī)科 學(xué)與技術(shù) 122 班學(xué) 號2012211643實(shí)驗(yàn)日期指導(dǎo)教師徐本柱成 績一、實(shí)驗(yàn)?zāi)康暮鸵? .理解線段的

33、性質(zhì)、叉積和后向回積。2 .掌握尋找凸包的算法。3 .綜合運(yùn)用計(jì)算幾何和搜索中的知識(shí)求解有關(guān)問題。二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容凸包：是一組點(diǎn)集中的子集， 這一子集形成的凸多邊形可以將點(diǎn)集中所有的點(diǎn)都圍住，并且這一凸邊形的面積是最小的。一種尋找凸包的算法：打包法首先，我們找出點(diǎn)集中最下方的點(diǎn)，如果這樣的點(diǎn)不止一個(gè)，就選用最左邊的點(diǎn)(如P0)。顯然，這個(gè)點(diǎn)(P0)是凸包子集中的一個(gè)點(diǎn)?？梢栽O(shè)想在 P0處拴了一根 皮筋的一端，另一端放在和 P0成水平位置的右側(cè)?，F(xiàn)在，將皮筋，沿逆時(shí)針方向轉(zhuǎn)動(dòng)，首先會(huì) 碰到P1,這樣就找到了另一個(gè)凸包子集中的點(diǎn)。以 P1為中心，做和P0 一樣的事，會(huì)發(fā)現(xiàn)，我 們將碰到P3,又一個(gè)

34、凸包的點(diǎn)。我們可以一直這樣做下去，直到再一次遇到P0,凸包就被找出來了。具體而言，在第一次找到 P0點(diǎn)之后，以P0為每個(gè)矢量的起點(diǎn)，其它的點(diǎn)為矢量的終點(diǎn)， 來比較任意兩個(gè)矢量的轉(zhuǎn)角，就可以對余下的點(diǎn)進(jìn)行按極角排序三、實(shí)驗(yàn)項(xiàng)目摘要1將講義第三章第三節(jié)中的凸包代碼上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。2完成講義第三章的課后習(xí)題，上機(jī)運(yùn)行并檢驗(yàn)結(jié)果。3思考：判線段相交時(shí)，如果有個(gè)線段的端點(diǎn)在另一條線段上，注意可能與另一條線段上的 端點(diǎn)重合，思考這樣的情況。4房間最短路問題：給頂一個(gè)內(nèi)含阻礙墻的房間，求解出一條從起點(diǎn)到終點(diǎn)的最最短路徑。房間的邊界固定在x=0,x=10,y=0和y=10。起點(diǎn)和重點(diǎn)固定在(0,5)和(1

35、0,5)。房間里還有0到18個(gè) 墻，每個(gè)墻有兩個(gè)門。輸入給定的墻的個(gè)數(shù)，每個(gè)墻的x位置和兩個(gè)門的y坐標(biāo)區(qū)間，輸出最短路的長度四、實(shí)驗(yàn)結(jié)果與分析(源程序及相關(guān)說明)3 .思考：用跨立方法，跨立的含義是：如果一條線段的一個(gè)端點(diǎn)在一條直線的一邊，另一個(gè)端 點(diǎn)在這條直線的另一端，我們就說這條線段跨立在這條直線上。線段相交滿足且只需 滿足如下兩個(gè)條件就可以了：1兩條線段相互跨立；2 條線段的一個(gè)端點(diǎn)在另一條線段上。如果兩線段相交，則兩線段必然相互跨立對方。若p1p2跨立p3P4 ,則矢量(p1 - p3 )和(p2 - p1 )位于矢量(p4 - p3 )的兩側(cè)，即(p1 -p3) X ( p4- p3

36、 ) * ( p2 -p3 ) X ( p4 - p3 ) < 0。上式可改寫成(p1 - p3 ) X ( p4-p3 ) * ( p4 - p3 ) X (p2 - p3) > 0。當(dāng)(p1 - p3 ) X ( p4- p3 ) = 0 時(shí)，說明(p1 - p3 )和(p4 - p3 ) 共線，但是因?yàn)橐呀?jīng)通過快速排斥試驗(yàn)， 所以p1 一定在線段p3P4上；同理，(p4 - p3 ) X(p2 - p3 ) = 0說明p2 一定在p3P4上。所以判斷p1p2跨立Q1Q2的依據(jù)是： (p1 - p3 ) X ( p4 - p3 ) * ( p4 - p3 ) X ( p2-p3

37、 ) >= 0。同理判斷 Q1Q2 跨立 P1P2的依據(jù)是：(p3 - p1 ) X ( p2 - p1 ) * ( p2 - p1 ) X ( p4 - p1 ) >= 0。代碼中函數(shù) bool segment_intersect(用于判斷p1、p2構(gòu)成的線段和p3、p4構(gòu)成的線段是否相交。 可以看出共五種情況兩覆段是相交而，應(yīng)之就輸出“ The two are Not intersected!4 .房間最短路問題：#include<iostream>#include<utility>#include<vector>innclude<al

38、gorithm>using namespace std;typedef pair<double,double> POINT;/線段double direction(POINT p,POINT p1,POINT p2)POINT v1,v2;v1.first=p2.first-p1.first;v1.second=p2.second-p1.first;v2.first=p1.first-p.first;v2.second=p1.second-p.second;return v1.first*v2.second-v1.second*v2.second;bool on_segmen

39、t(POINT p,POINT p1,POINT p2)double min_x=p1.first<p2.first?p1.first:p2.first;max_x=p1.first>p2.first?p1.first:p2.first;double min_y=p1.second<p2.second?p1.second:p2.second;double max_y=p1.second>p2.second?p1.second:p2.second;if(p.first>=min_x&&p.first<max_x&&p.second>=min