全國(guó)一模擬day2聯(lián)考

1、Task MARMAR.PAS/EXE在 2051 年，若干火星探險(xiǎn)隊(duì)探索了這顆紅色行星的不同的區(qū)域并且制作了這些區(qū)域的地圖?，F(xiàn)在, BaSA ( Baltic 空間機(jī)構(gòu))有一個(gè)雄心勃勃的計(jì)劃：他們想制作一張整個(gè)行星的地圖。為了考慮必要的工作，他們需要知道地圖上已經(jīng)存在的全部區(qū)域的大小。你的任務(wù)是寫(xiě)一個(gè)計(jì)算這個(gè)區(qū)域大小的程序。任務(wù)編程：從輸入文件 mar.in地圖形狀的描述，計(jì)算地圖覆蓋的全部的區(qū)域，輸出到輸出文件 mar.out。輸入輸入文件 mar.in 第一行包含一個(gè)整數(shù) N (1=N=10000)，表示到的地圖數(shù)目。以下 N 行每行描述一張地圖。每行包含 4 個(gè)整數(shù) x1，y1，x2

2、和 y2(0=x1x2=30000， 0=y1y2=30 000)。數(shù)值(x1，y1)和(x2，y2)是坐標(biāo)，分別表示繪制區(qū)域的左上角和右下角坐標(biāo)。每張地圖是矩形的，并且它的邊是平行與 X 坐標(biāo)軸或 Y 坐標(biāo)軸的。輸出輸出文件 mar.out 應(yīng)該包含一個(gè)整數(shù)，表示探索區(qū)域的總面積(即所有矩形的公共面積)。樣例MAR.IN210 10 20 2015 15 25 30MAR.OUT225DRIVING源程序名可執(zhí)行文件名輸入文件名輸出文件名DRIVING.? (pas, DRIVING.exe DRIVING.inDRIVING.outp)在很多很多年以后，人們都是乘著飛碟在城市當(dāng)中穿梭的；而

3、那時(shí)的摩天大樓非常得高，高得一般的飛碟不可能從它的上面穿越。所以，飛碟只能繞著大樓走。現(xiàn)在需要你考慮一個(gè)問(wèn)題：怎樣讓飛碟從 a 到 b 走的路最少呢？考慮一個(gè)簡(jiǎn)化的模型：假設(shè)飛碟是圓形的，它的半徑是 r，因此飛碟的位置可以用圓心所在位置來(lái)表達(dá)。城市中的摩天大樓被 OXY 坐標(biāo)軸表達(dá)，每一幢大樓一定是一個(gè)長(zhǎng)方形，并且其邊平行于 X 軸和Y 軸。飛碟可以和大樓相碰，但是不能進(jìn)入大樓。即相應(yīng)的圓可以和長(zhǎng)方形相切，但不可以相交。出發(fā)點(diǎn) a 和目的地 b 都用坐標(biāo)（Xa，Ya），（Xb，Yb）表達(dá)。飛碟走過(guò)路程的長(zhǎng)度用圓心移動(dòng)的軌跡的長(zhǎng)度來(lái)表達(dá)。下面有一些例子：其中黑線標(biāo)明的就是飛碟移動(dòng)的最短路線。輸入

4、第一行兩個(gè)整數(shù)，r（=100）和 n(=2。（如右所示）這么好的一段材料浪費(fèi)了怪可惜的，King 決定好好加工一番做成一件藝術(shù)品。但他不是純藝術(shù)家，他覺(jué)得每一件作品都應(yīng)該有實(shí)用價(jià)值（否則只是華而不實(shí)），具有實(shí)用性的藝術(shù)品是他設(shè)計(jì)的理念。根據(jù)這塊木板的鋸齒狀，King 想到了每天起床后都要用到的一件日用品，“對(duì)，就把它做成梳子！”他的設(shè)想是：用刻刀將某些上端的格子挖掉（如果把某個(gè)格子挖掉，那么這個(gè)格子上方的格子也必須被挖掉，但不能把一列中的格子全都挖掉），使得剩L=9A=(4,4,6,5,4,2,3,3,5)123456789下木板“規(guī)則鋸齒形”（這樣才好梳頭）。例如，對(duì)于上圖，挖掉第 3，7，

5、8 列最上面 1個(gè)格子，第 5 列最上面 2 個(gè)格子后，剩下的區(qū)域就“規(guī)則鋸齒形”（如右圖）。一個(gè)鋸齒形稱為“規(guī)則鋸齒形”當(dāng)且僅當(dāng)它的上邊界（圖中紅色曲線所示）的拐彎序列不包含“010”或者“101”。圖中紅色曲線的拐彎序列為：“011001”，（其中 0 代表往左拐，1 代表往右拐）沿著曲線的最左端往右走，先左拐，再右拐，接著右拐，然后左拐，繼續(xù)左拐，最后右拐。為了最大限度的減少浪費(fèi)，King 希望做出來(lái)的梳子面積最大。這樣一來(lái)，設(shè)計(jì)梳子的任務(wù)就變得非常復(fù)雜了不過(guò)這是對(duì)于藝術(shù)家來(lái)說(shuō)，對(duì)于你來(lái)說(shuō)，不就是小菜一碟嗎？輸入數(shù)據(jù)：第一行一個(gè)整數(shù) L；第二行 L 個(gè)正整數(shù)A1,A2,AL。1Ai=108。輸出數(shù)據(jù)：輸出一個(gè)整數(shù) D，表示：為使梳子的面積最大，最少需要從木板上挖掉的格子數(shù)。數(shù)據(jù)范圍：4=L=100000。有 50%的數(shù)據(jù)滿足 L=104。輸入示例#1：94 4 6 5 4 2