網(wǎng)上找一些-動(dòng)態(tài)算法

2、遞歸地定義最優(yōu)值（寫出動(dòng)態(tài)規(guī)劃方程2、子問題：在用遞歸算法自頂向下解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反對(duì)fn1(xn1)初始化 {邊界條件fork:=ndownto1for每一個(gè)xk∈Xkforuk∈Uk(xkdo {∞或xk t:=φ(fk1(xk iftfk(xkthenfk(xk):=t;{計(jì)算fk(xk)的最優(yōu)值}t:=一個(gè)極值 {∞或for每一個(gè)x1∈X1iff1(x1)比t更優(yōu)then <!--#EndEditable--不同．描述階段的變量稱為階段變量。在多數(shù)情況下，階段變量是離散的，用k面的例子中，第一個(gè)階段就是點(diǎn)A，而第二個(gè)階段就是點(diǎn)A到點(diǎn)B，第三個(gè)階段是點(diǎn)B到點(diǎn)C，而第四個(gè)階段是點(diǎn)C到點(diǎn)D。狀態(tài)：狀態(tài)表示每個(gè)階段開始的自然狀況或客觀條件，它不以人們的意志為轉(zhuǎn)移，也稱為不可控面的例子中，第一個(gè)階段有一個(gè)狀態(tài)即A，而第二個(gè)階段有兩個(gè)狀態(tài)B1和B2，第三個(gè)階段是三個(gè)狀態(tài)C1，C2和C3，而第四個(gè)階段又是一個(gè)狀態(tài)D。無后效性：要求狀態(tài)具有下面的性質(zhì)：如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過程也就確定了。換句話程的每一次實(shí)現(xiàn)x(k+1)x(k)ku(k)的值變化而變化，那么可以把這一關(guān)系看成最優(yōu)性原理:實(shí)際上是要求問題的最優(yōu)策略的子策略也是最優(yōu)。讓通過對(duì)前面的例子再分析來具體說明這一點(diǎn)：從A到D，知道，最短路徑是AàB1àC2àD，這些點(diǎn)的選擇構(gòu)成了這個(gè)例子的最優(yōu)策略，根的最短路徑……──事實(shí)正是如此，因此認(rèn)為這個(gè)例子滿足最優(yōu)性原理的要求?，F(xiàn)有一圖G，求從起點(diǎn)VsVe的最短距離。設(shè)：VjVsVjM(i,j)───Vi到Vj的非負(fù)長(zhǎng)度?！齎s↓ | | | （Vk與Vj之間相連 | Sj小于 ||Y|N|||-------------------|||↓||H（j）←Vk 注意：1.2.只有隊(duì)列的首結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)時(shí)，才可停止計(jì)算。否則得出的不一定是最優(yōu)解。N*N(<=100)M，M[A1，B1]開始到M[A2，B2]結(jié)束的相鄰項(xiàng)序列.兩個(gè)項(xiàng)M[I，J]和M[K，L]相鄰的件是指滿足如下情況之一：I=K+-1I=KJ=L+-1任務(wù)：從文件中輸入矩陣MK(K<=4)M[A1，B1]M[A2，B2]的值。對(duì)于每一組M[A1，B1]和M[A2，B2]，求一相鄰項(xiàng)序列，使得相鄰的絕對(duì)值之和為最小。49612───每行N個(gè)數(shù)據(jù)，共N87359117324114A1,B1A2,B2K行223117───第一組數(shù)據(jù)相鄰的絕對(duì)值之和的最小值47911兩個(gè)頂點(diǎn)的最短路問題。設(shè)：Sum[I,J]為從起點(diǎn)VsM[I,J]的最短距離。H[I,J]記錄結(jié)點(diǎn)M[I,J]的前趨結(jié)點(diǎn)。LProgramgconstfang:array[1..4,1..2]ofinteger=((-1,0),(0,-sum:Array[1..100,1..100]ofinteger;m:Array[1..100,1..100]ofinteger;h:Array[1..100,1..100,1..2]ofbyte;procedurec:array[1..100]ofinteger;

flag:=true;a:=1;c[a]:=m[x2,y2];x:=x2;y:=y2;whileflagdo

a:=a+1;x3:=x;y3:=y;x:=h[x3,y3,1];y:=h[x3,y3,2];if(x=x1)and(y=y1)thenflag:=false; {求出整條路徑，放入數(shù)組C中}wrin(f2,zz,'',sum[x2,y2]);forb:=adownto1dowrite(f2,c[b],'');{打印結(jié)果}wrin(f2);procedureadd(x,y,i:integer;<I>var</I>

newe^.x:=x;ifi=0thenl^.next:=e{加入隊(duì)列}elsebeginf:=l;g:=f^.next;flag:=true;fora:=1toidoifsum[g^.x,g^.y]>sum[x,y]thene^.next:=g;f^.next:=e;flag:=false;a:=i;

f:=f^.next;

ifflagthenf^.next:=e;{加入隊(duì)列}procedure

fillchar(sum,sizeof(sum),255);Sum1}sum[xz,yz]:=0;{置起點(diǎn)Sum值為0}new(e);e^.x:=xz;new(l);l^.next:=e;c:=1;{現(xiàn)在隊(duì)列結(jié)點(diǎn)個(gè)數(shù)}whileflagdov:=l^.next;dispose(l);{取出首結(jié)點(diǎn)l:=v;c:=c-1;{指針下移一位，結(jié)點(diǎn)個(gè)數(shù)減一}x:=v^.x;y:=v^.y;if(x=x2)and(y=y2)thenflag:=false;ifflagthenfora:=1to4do 1)

if(x1>0)and(x1<=n)and(y1>0)andsj:=sum[x,y]+abs(m[x,y]-if(sj<sum[x1,y1])orh[x1,y1,1]:=x;add(x1,y1,c,l);c:=c+1;{結(jié)點(diǎn)個(gè)數(shù)加一}

assign(f1,'gassign(f2,'g974.out');reset(f1);rewrite(f2);readln(f1,n);fora:=1tondoforb:=1tonread(f1,m[a,b]);readln(f1);end;{讀入數(shù)組}readln(f1,k);fora:=1tokdo

readln(F1,x1,y1,x2,y2);{讀入任務(wù)}態(tài)的轉(zhuǎn)移,一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的,故有"動(dòng)態(tài)"的含義,稱這種解決多階段決策Catcher防衛(wèi)(Gprograma:array[1..4000]ofinteger;{高度數(shù)組}c:array[1..4000,1..2]ofinteger;procedurereadfile;assign(f,'catcher.dat');reset(f);fori:=1tonumdoprocedurework;fillchar(c,sizeof(c),0);c[num,1]:=1;fori:=num-1downto1don:=0;forj:=i+1tonumif(a[i]>a[j])and(max<1+c[j,1])thenbeginn:=j;max:=1+c[j,1];end;c[i,1]:=max;c[i,2]:=n;wrin;wrin('Max:',max);{打印最大值}max:=0;n:=0;fori:=1tonumifc[i,1]>maxthenbeginmax:=c[i,1];n:=i;wrin(n,'');n:=c[n,2];untiln=0;readfile;work;Perform巡回演出(FlutePhlharmoniker樂團(tuán)2000準(zhǔn)備到Harp做一次大型演出,本著普及古典音樂的目的,樂團(tuán)指Harp(2,3,...n)n-12(1,3,4...n)的航班,如此下去.應(yīng)的兩個(gè)城市的航班的價(jià)格,價(jià)格為零表示那天兩個(gè)城市之間沒有航班.例如"375080"表示第一75KOI,80KOI75KOI,第五天沒有航班,如此循環(huán).輸入文件由n=k=0的場(chǎng)景結(jié)束.36213037507120110010011012046070603023201000初看這道題,很容易便可以想到動(dòng)態(tài)規(guī)劃,因?yàn)榈趚yx-1規(guī)劃的無后效性原則,即只與上一個(gè)狀態(tài)相關(guān)聯(lián),而某一天xS=C[(x-1)modm+1].值,C[i,j,l]ij城市間第lA[i,j]=Min{A[i-1,l]+C[l,j,i](l=1..nprograma:array[1..1000,1..10]ofinteger;c:array[1..10,1..10]ofrecord{航班價(jià)格數(shù)組}t:array[1..30]ofinteger;e:array[1..1000]ofinteger;procedurework;fori:=1tondoifthena[1,i]:=c[1,i].t[1];fori:=2tokdoforj:=1tondoforl:=1tondoifand(c[l,j].t[(i-1)modc[l,j].num+1]<>0)and((a[i,j]=0)or(a[i-1,l]+c[l,j].t[(i-1)modc[l,j].num+1]<a[i,j]))thena[i,j]:=a[i-1,l]+c[l,j].t[(i-1)modc[l,j].num+1];{賦值}e[p]:=a[k,n];pprocedurereadfile;assign(f,'PERFORM.DAT');reset(f);assign(fout,'PERFORM.OUT');rewrite(fout);readln(f,n,k);p:=0;while(n<>0)and(k<>0)dofori:=1tondoforj:=1toi-1doforl:=1toc[i,j].numdoforj:=i+1tondoforl:=1toc[i,j].numdofori:=1top-1do且同時(shí)求出了到中間狀態(tài)的最優(yōu)值,這對(duì)于很多實(shí)際問題來說是很有用的.這幾年,動(dòng)態(tài)規(guī)劃已在市信少.(G''99則F[I,J]=Min{Max{F[i-1,k],Sum[k+1,J]}}1<=k<=j-（GDKOI'2000對(duì)于任意一個(gè)整數(shù)數(shù)列，可以在每?jī)蓚€(gè)整數(shù)中間任意放一個(gè)符號(hào)‘+’或‘-’，這樣就可以可以構(gòu)造8個(gè)表達(dá)式：17+5+(-17+5+(-21)-17+5-(-17+5-(-21)-17-5+(-17-5+(-21)-15=-17-5-(-17-5-(-21)-對(duì)于一個(gè)整數(shù)數(shù)列來說，能通過如上的方法構(gòu)造不同的表達(dá)式，從而得到不同的數(shù)值，如果該數(shù)值能夠被k。在上面的例子中，該數(shù)列能717+5+(-21)-15=-14)，但不能被5?，F(xiàn)在數(shù)據(jù)存放在當(dāng) 文件的第一行是一個(gè)整數(shù)M，表示有Mm每個(gè)子任務(wù)有兩行。第一行是兩n和K（1<=n<=1000,2<=k<=100），n和k中間有一個(gè)空格。n數(shù)列中整數(shù)的個(gè)數(shù)；k是需要你判kn間用空格隔開，每個(gè)整數(shù)的絕對(duì)值都不超過10000。答案輸出到當(dāng) "Divisible"，否則輸出"NotDivisible"│輸入文件：div．in│輸出文件：div．out ││4 │Not││175-21 │4 │175-21 根據(jù)同余的性質(zhì)注意到[(Amodk)+B]modk=(A+B)modFalseF[i-F[i][(data[i]+v)modTrueF[i-第二行N個(gè)數(shù),為Ｎ種物品重量；兩個(gè)數(shù)用空格分隔；第三行NN4234713592141后，對(duì)應(yīng)的子問題中的重復(fù)，這樣就將重復(fù)地求解；在第一次遇到重復(fù)時(shí)把它解決，并將解保存起來，以備后面。動(dòng)態(tài)規(guī)劃法常用來求一個(gè)問題在某種意義下的最優(yōu)解。--譯者）則F[i]={maxing 當(dāng)F[i-weigh[k]]=maxMax{F[i-weigh[k]]+worth[k]}F[i-weigh[k]]>0用帶奶的總時(shí)間。找到這樣一組歌曲的集合，使得歌曲的總長(zhǎng)度不超過給Bessie擠奶的總時(shí)間且使Bessie的合的值的和最大，且其尺寸的和受某些限制所約束。集合中任何一個(gè)特定的項(xiàng)目的總數(shù)目/尺寸過的背包是一只水桶，取0.473升的原油，0,263升的飛機(jī)和0,264升的煤油就是有意義的。這是形式N復(fù)雜度是O(N2)。否比當(dāng)前最好的大小為K+S的背包更符合條件。一個(gè)語言L，如果有一架非確定圖靈機(jī)MP(nInw，MP(n)w，則稱LNPL損失的條件下，縮短數(shù)字（如果你有3,5個(gè)物品，你可以僅用3）。如果值都是同一個(gè)，那么如果能被放入所有背包中的物品的最大值是n，則存在使用n個(gè)最小物品的分?jǐn)?shù)膨脹[1998USACONational欄[1999USACOSpring各種長(zhǎng)度的木板（至多50個(gè)）。已知木材店木板的長(zhǎng)度，要的圍欄長(zhǎng)度，計(jì)算建所用的圍你在Beaver郡中部一百英里有一個(gè)的城市中，想將你的油箱裝滿好能到達(dá)RitaBlanca。幸運(yùn)地是，這個(gè)小鎮(zhèn)有兩三個(gè)，但它們的油像要用光了。已知每個(gè)的油價(jià)，每個(gè)的油量，計(jì)算為了花最少的錢，應(yīng)該從每個(gè)買多少。分析：這是一個(gè)小數(shù)背包問題，背包是油箱，物品是。3A，B，C010x，y，z，使得A(x)+B(y)+C(z)為最大，并且滿足x2+y2+z2〈ＮX0123456789A(x)24711131518221815B(x)5 53C(x)81217在一個(gè)圓形操場(chǎng)的四周擺放著N堆石子(N<=100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選取相鄰的兩堆合并成新的一堆,并將新的一堆的石子數(shù),記為該次合并的得分.編一程序,由文件讀入堆棧數(shù)N(!)選擇一種合并石子的方案,使用權(quán)得做N－1次合并,得分的總和最小;(2)選擇一種合并石子的方案,使用權(quán)得做N－1次合并,得分的總和最大;從第一N行為得分最小的合并方案.第N+1行是空行.從第N+2行到第2N+1行是得分最大合并方案.每種合并方案N行表示,其i行(1<=i<=N)表示第i次合并前各堆的石子數(shù)(依順時(shí)針次序輸出,哪一堆44 ９－８－５ 設(shè)有一排數(shù)，共ｎ個(gè)，例如：22 .任意2個(gè)相鄰的數(shù)可以進(jìn)行歸并歸并的代價(jià)為該兩個(gè)數(shù)的和,經(jīng)過不斷的歸并,最后歸為一堆,而全部歸并代價(jià)的和稱為總代價(jià),給出一種歸并算法,使總代價(jià)為最小.412 2ICU(ICU是信息學(xué)競(jìng)賽的貨幣的單位）;一個(gè)花瓶的價(jià)格是5ICU。為了吸引的顧客，商店提供了特殊價(jià)。特殊商品是把一種或幾種商品分成一組。并降價(jià)銷售。例如:365ICU;2110ICU12ICU編一個(gè)程序，計(jì)算某個(gè)顧客所購商品應(yīng)付的費(fèi)用。要充分利用價(jià)以使顧客付款最小。請(qǐng)注意，你不能變更顧客所購商品的種類及數(shù)量，即使增加某些商品會(huì)使付款總數(shù)減小也不允許你作出任何變更。假定各種商品價(jià)格用價(jià)如上所述，并且某顧客物品為:3朵花和2個(gè)花瓶。那么顧客應(yīng)付款為14ICU1朵花加2個(gè)花瓶:價(jià):102朵花正常價(jià):4商店提供的商品及價(jià)格（文件名為OFFER．TXT）。兩個(gè)文件中都只用整數(shù)。行，每行中含3個(gè)數(shù)C，K，P。C代表商品的編碼（每種商品有一個(gè)唯一的編碼），1≤C≤999。K代表該種商品總數(shù)，1≤K≤5。P是該種商品的正常單價(jià)（每件商品的價(jià)格），1≤P≤999。請(qǐng)注意，購物筐中最多可放5*5＝25件商品。第二個(gè)文件OFFER．TXT的格式為:第一行是一個(gè)數(shù)字S（0≤S≤99），表示共有S種。下面共S行，每一行描述一種商品的組合品的種類。下面接著是幾個(gè)數(shù)字對(duì)（C，K），其中C代表商品編碼，1≤C≤999。K代表該種商品在此組合中的數(shù)量，1≤K≤5。本行最后一個(gè)數(shù)字P（1≤P≤9999）代表此商品組合的價(jià)。當(dāng)然，價(jià)要低于該組合品正常價(jià)之總和。OUTPUT．TXT（占一行），（輸入文件指明所購商│││ ││2││││││７３２││175│││││８２５││27│82│└────────┘的序列，對(duì)于給定的基元的集合P，如果可以從中選出N個(gè)基元P1，P2，…Pn，將它們各自對(duì)應(yīng)的字符串依次聯(lián)接后得到一個(gè)字符串S，稱S可以由基元集合P字符串的前K個(gè)字符稱為該字符串的前綴，其長(zhǎng)度為K.請(qǐng)寫一個(gè)程序，對(duì)于輸入的基元集合P和字符串T，求出一個(gè)可以由基元集合P構(gòu)成的字符串T的前綴，INPUT.TXT文件DATA.TXT描述要處理的字符串T，每一行行首有一個(gè)大寫英文字母，算法：動(dòng)態(tài)規(guī)劃題型：II型難度：4編程時(shí)間：4旅游有如下規(guī)則計(jì)算精確到分（1元=100分）。編寫程序估計(jì)實(shí)際行駛在某路線所需的最小費(fèi)用。 答案輸出到當(dāng) 輸入文件 輸出文件 38.0915.722.120.87 1、每艘船在出發(fā)的一瞬間提交航行計(jì)劃（提交和出發(fā)的時(shí)間差可以忽略23（兩港口間的直達(dá)航線）上只能有一艘船，因此，一艘船在出發(fā)的瞬間發(fā)現(xiàn)某航45674234523：45，速度單位用節(jié)（海里/小時(shí)）表示。在計(jì)算時(shí)間時(shí)，中間結(jié)果應(yīng)從當(dāng)前下的文本文件“LANE.DAT”讀入數(shù)據(jù)。輸入的數(shù)據(jù)一定有解，且不會(huì)出現(xiàn)00：00的情第三行開始NNXNN（單位為海里），整數(shù)間以空格分隔（若為0表示兩港口沒有直達(dá)航線相連）；答案輸出到當(dāng)前下的文本文件“LANE.OUT3輸入文件 輸出文件 0 0 00 0 0 04 行n，侍衛(wèi)所需的經(jīng)費(fèi)k，該邊的兒子數(shù)m，接下來m個(gè)數(shù)，分別是這個(gè)節(jié)點(diǎn)的m個(gè)兒子的標(biāo)號(hào) 對(duì)于一個(gè)n（0<n<=1500）1nSramoc(K,M)表示用數(shù)字0、1、２…、K-1MK、M，Sramoc(K,M)。例如K=2，M=7，Sramoc(2,7)=1001。Sramoc(K,M)到SRAMOC.OUT。7Timelimit:1Seconds Memorylimit:32768KTotalSubmit:843 AcceptedSubmit:303用它的數(shù)字乘以它左邊和右邊的數(shù)，所以不允許拿第1張和最后1張牌。最后一次移動(dòng)后，這里只剩下兩10150205，1、20、50，6Timelimit:1Seconds Memorylimit:32768KTotalSubmit:172 AcceptedSubmit:4534510900旅行家來到了一個(gè)著名的旅游勝地。這里的風(fēng)景很好，旅行家想自己把所有的路都走一遍，這樣可以這個(gè)旅游勝地一共有n同的標(biāo)準(zhǔn)?，F(xiàn)在請(qǐng)你寫一個(gè)程序，為旅行家設(shè)計(jì)一條路線，使得這條路線覆蓋盡可能多的道路（不包括乘車經(jīng)過的），輸入包括了多個(gè)測(cè)試數(shù)據(jù)。每個(gè)測(cè)試數(shù)據(jù)開頭是一個(gè)整數(shù)n（1<=n<=100），表示路口總數(shù)。接下來一行包括了n數(shù)m，表示道路總數(shù)。之后的m行包括兩個(gè)整數(shù)x，y（1<=x，y<=n）分別表示該道路連接的兩個(gè)路口。路口按照輸入順序從小到大依次編5358761213152534356邀請(qǐng) 。但是，正如你所知，比較傲慢，而且不能 每一組的第一行有整數(shù)N（<=300）和M（<=5000）。以下的N行是N個(gè) 的名字，都不超過10個(gè)字符，而且中間不含空格。接下來的M行是列舉有的，每行有2個(gè) 輸出文件 行輸出一個(gè)整數(shù)，表示第i組有多少位 。第2i+1行輸出第I組的名字，用空格分開。你可以假設(shè)一定要將這些分成4組，不能比4組少。4AAABBC6AAABBCDCase1Case2A1D時(shí)間限制：100ms農(nóng)民有如下型號(hào)的牛奶容器：10，2，1，1/4，1/8，1/16。編寫一個(gè)程序能計(jì)算用這些容器取X牛奶共有多少不同方法。在所有的數(shù)據(jù)中，X都是整數(shù)且5 .正在玩軍事，現(xiàn)在他有N個(gè)洲際。他需要在最短的時(shí)間內(nèi)，用這N個(gè)洲際摧毀敵方N個(gè)目標(biāo)，1個(gè)洲際只能摧毀1個(gè)目標(biāo)。覺得給每個(gè)洲際確定目標(biāo)是一件很麻煩的事情。請(qǐng)你編程幫助給每個(gè)洲際確定目標(biāo)，使每個(gè)洲際到其目標(biāo)的距離之和為最小。第一行為N(N≤12)第2行到N+1行，每一行包含一個(gè)坐標(biāo)(X,Y)，表示一個(gè)洲際的位置。N+22N+1X,Y)，表示一個(gè)目標(biāo)的位置。其中-10000≤X,Y≤10000，X,Y為整數(shù)。1-1--2-2尋找在宇宙中居住的方法。找到合適的居住環(huán)境是一題，因?yàn)橛钪嬷谐錆M著各種各樣的，比如在某個(gè)區(qū)域內(nèi)經(jīng)常有小行星或隕石出沒（這些都稱作飛行物）?？茖W(xué)家們經(jīng)過觀察發(fā)現(xiàn)飛行物的飛行軌跡要么互相平行要么互相垂直（在三中）。所以可以把宇宙看作是許多等大的正方體格子所組成的大長(zhǎng)方體，凡是有飛行物經(jīng)過的格子都不是理想的居住地?，F(xiàn)在給你宇宙空間的大小和飛行物的飛行軌跡，請(qǐng)你編程幫助科學(xué)家們找到一個(gè)最大的理想居住地，且這個(gè)居住地是一個(gè)正方體。輸入以下有N行，每一行為：kind,x,y,z,t。例如：x13y1232(1,2,3z1231(1,2,3)到(1,2,1)0≤N≤100。0<x0,y0,z0≤20且x0,y0,z0-x0≤x≤x0;-y0≤y≤y0;-z0≤z≤z0;且x,y,z當(dāng)kind為x時(shí)，-x0≤t≤x0輸出文件時(shí)間限制：2秒10103x-100y0-0z0010-10不過，這個(gè)醫(yī)生在開藥方的時(shí)候，有一個(gè)固定的標(biāo)準(zhǔn)模式。他有一個(gè)藥材庫，里面有n種用n1，2，……nn現(xiàn)在，有一個(gè)關(guān)于這個(gè)醫(yī)生的藥方，藥方中寫有P整數(shù)p，表示具體的一個(gè)藥方的藥的數(shù)目。繼續(xù)下來的p行，每行有一個(gè)整數(shù)，表示這個(gè)藥方第i個(gè)藥被鑒別出是k；如果k0，表示這個(gè)藥還沒有鑒別出來。輸出文件的第一行是一個(gè)整數(shù)m，表示總共可以構(gòu)造出mm5241352312403002235435從文件l計(jì)算日費(fèi)用的最小值l結(jié)果寫入文件文件BOR。IN第一行的整數(shù)N表示城市的個(gè)數(shù)，5<=N<=10000(假定城市都是沿高速公路編號(hào)，相鄰的城市也緊接。城市一與城市N相鄰）。接下來的N行每行為倆個(gè)用單個(gè)空格隔開的非負(fù)的距離（用英里做度量）10000001000612231252123Squares（正方形TimeLimit:0.5secondMemoryLimit:1000K給出N(0<N<100)個(gè)正方形和點(diǎn)P.點(diǎn)P和正方形的最短線段是指點(diǎn)P線或區(qū)域的最短連線。如果P在正方形，那么它們之間的距離為0.有些正方形的的頂點(diǎn)是重第一行為數(shù)N.接下來的N行包含有4個(gè)整數(shù)，范圍在(-9999,9999).前2個(gè)表示一個(gè)頂點(diǎn)的X,YPx，y序給出的。當(dāng)有兩個(gè)正方形到點(diǎn)P的距離是相等時(shí)，序號(hào)小的先輸出。當(dāng)比較距離時(shí)，請(qǐng)用1E-14SampleInput00103100Sample1PensilsandCircles(鉛筆和圓）TimeLimit:1secondMemoryLimit:一個(gè)老和一個(gè)老坐在桌子上寫信。在桌子上有N只鉛筆，用坐標(biāo)(xi,yi)表示。鉛筆的直3<=N<=5000.n你必須輸出圓經(jīng)過的三支鉛筆的坐標(biāo)。在圓內(nèi)有(N-3)/2支鉛筆，在圓外也有(N-3)/2支鉛筆。若沒有解決方案，輸出"Nosolution".若有多種解決方案，則任輸出一種。SampleInput00102-211102-3-Sample012TimeLimit:1secondMemoryLimit:1000KAB接下來的就是地鐵的描述。第一行為一整數(shù)N，它是地鐵站的數(shù)量。假設(shè)N不超過200N行，每行包含兩個(gè)浮點(diǎn)數(shù)(第i-行為第i-個(gè)地鐵站的坐標(biāo))。接下來的描述表示哪兩個(gè)站相連，每一最后為點(diǎn)A和B的坐標(biāo)，一行一個(gè)。第一個(gè)為的地鐵站的數(shù)量，后跟著一系列地鐵站的Sample1400109099121324001010SampleOutput4421車廂順序，當(dāng)輸入行的第一個(gè)數(shù)為0，表示文件結(jié)束。432060TimeLimit:2在羅馬尼亞，有K個(gè)無線電發(fā)射站，位于不同的地方和海拔高度。每個(gè)站都有一定的輻射范圍，也就是說，可以發(fā)射信號(hào)的最遠(yuǎn)距離。想在某地建一個(gè)接收站，以使它能夠接收所有K個(gè)發(fā)射站的信羅馬尼亞被劃分成M*N個(gè)矩陣，i行和j列的值表示的是相應(yīng)區(qū)域的海拔高度。矩陣的小方格的邊長(zhǎng)為1.所有的K個(gè)發(fā)射站位于地圖上的不同的坐標(biāo)并且和相應(yīng)區(qū)域的海拔高度是一樣的你的任務(wù)是計(jì)算建接收站可以有多少種方案（可能）。注意：如果接收站位于行i和列j，海拔高度為h1和h2(h1<>h2),這就算兩種不同的方案。M,N(1<=M,N<=50) K(1<=K<=min(,1000)),