青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 7,comments - 3,trackbacks - 0

 1043: Atlantis


ResultTIME LimitMEMORY LimitRun TimesAC TimesJUDGE
3s8192K431155Standard

There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.

Input

The input file consists of several test cases. Each test case starts with a line containing a single integer n(1 < n < 100) of available maps. The n following lines describe one map each. Each of these lines containsfour numbers x1;y1;x2;y2 (0 < x1 < x2 < 100000;0 < y1 < y2 < 100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.The input file is terminated by a line containing a single 0. Don’t process it1.

Output

For each test case, your program should output one section. The first line of each section must be “Testcase #k”, where k is the number of the test case (starting with 1). The second one must be   “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.

Output a blank line after each test case.

Sample Input

2
10 10 20 20
15 15 25 25.5
0

Sample Output

Test case #1
Total explored area: 180.00


題目的意思是給定n個矩形的2n個坐標,求矩形的覆蓋面積。如果開一個大的bool數組,將覆蓋過的部分更新為true,再從頭到尾掃描一遍,在坐標范圍比較小的情況下,可以求解。但是如果坐標x,y的取值范圍很大,比如[-10^8,10^8],用上面這個方法就不能求解了;而且坐標還有可能是實數,上面的方法就更加不可行了,需要尋找一種新的解法,就是下面要說到的“離散化”。
    注意到要表示一個矩形,只需要知道其2個頂點的坐標就可以了(最左下,最右上)??梢杂?個數組x[0...2n-1],y[0...2n-1]記錄下矩形Ri的2個坐標(x1,y1),(x2,y2),然后將數組x[0...xn-1],y[0...2n-1]排序,為下一步的掃描線作準備,這就是離散化的思想。這題還可以用線段樹做進一步優化,但是這里只介紹離散化的思想。
    看下面這個例子:有2個矩形(1,1),(3,3)和(2,2),(4,4)。如圖:
    圖中虛線表示掃描線,下一步工作只需要將這2個矩形覆蓋過的部分的bool數組的對應位置更新為true,接下去用掃描線從左到右,從上到下掃描一遍,就可以求出矩形覆蓋的總面積。
    這個圖對應的bool數組的值如下:
    1 1 0                       1 2 3
    1 1 1       <---->       4 5 6
    0 1 1                       7 8 9

代碼:

#include<stdio.h>
#include
<iostream>
#include
<algorithm>
#define MAXN 201
using namespace std;

struct Node
{
    
int l, r;//線段樹的左右整點
    int c;//c用來記錄重疊情況
    double cnt, lf, rf;//
    
//cnt用來計算實在的長度,rf,lf分別是對應的左右真實的浮點數端點
} segTree[MAXN * 3];
struct Line
{
    
double x, y1, y2;
    
int f;
} line[MAXN];
//把一段段平行于y軸的線段表示成數組 ,
//x是線段的x坐標,y1,y2線段對應的下端點和上端點的坐標
//一個矩形 ,左邊的那條邊f為1,右邊的為-1,
//用來記錄重疊情況,可以根據這個來計算,nod節點中的c

bool cmp(Line a,Line b)//sort排序的函數
{
    
return a.x < b.x;
}

double y[MAXN];//記錄y坐標的數組
void Build(int t,int l,int r)//構造線段樹
{
    segTree[t].l 
= l;
    segTree[t].r 
= r;
    segTree[t].cnt 
= segTree[t].c = 0;
    segTree[t].lf 
= y[l];
    segTree[t].rf 
= y[r];
    
if (l + 1 == r) return;
    
int mid = (l + r) >> 1;
    Build(t 
<< 1, l, mid);
    Build(t 
<< 1 | 1, mid, r);//遞歸構造
}
void calen(int t)//計算長度
{
    
if (segTree[t].c > 0)
    {
        segTree[t].cnt 
= segTree[t].rf - segTree[t].lf;
        
return;
    }
    
if (segTree[t].l + 1 == segTree[t].r)
        segTree[t].cnt 
= 0;
    
else
        segTree[t].cnt 
= segTree[t << 1].cnt + segTree[t << 1 | 1].cnt;
}
void update(int t, Line e)//加入線段e,后更新線段樹
{
    
if (e.y1 == segTree[t].lf && e.y2 == segTree[t].rf)
    {
        segTree[t].c 
+= e.f;
        calen(t);
        
return;
    }
    
if (e.y2 <= segTree[t << 1].rf)
        update(t 
<< 1, e);
    
else
    
if(e.y1 >= segTree[t << 1 | 1].lf)
        update(t 
<< 1 | 1, e);
    
else
    {
        Line tmp 
= e;
        tmp.y2 
= segTree[t << 1].rf;
        update(t 
<< 1, tmp);
        tmp 
= e;
        tmp.y1 
= segTree[t << 1 | 1].lf;
        update(t 
<< 1 | 1, tmp);
    }
    calen(t);
}
int main()
{
    
int i, n, t, iCase = 0;
    
double x1, y1, x2, y2;
    
while(scanf("%d"&n) && n)
    {
        iCase
++;
        t 
= 1;
        
for(i = 1; i <= n; i++)
        {
            scanf(
"%lf%lf%lf%lf"&x1, &y1, &x2, &y2);
            line[t].x 
= x1;
            line[t].y1 
= y1;
            line[t].y2 
= y2;
            line[t].f 
= 1;
            y[t] 
= y1;
            t
++;
            line[t].x 
= x2;
            line[t].y1 
= y1;
            line[t].y2 
= y2;
            line[t].f 
= -1;
            y[t] 
= y2;
            t
++;
        }
        sort(line 
+ 1, line + t, cmp);
        sort(y 
+ 1, y + t);
        Build(
11, t - 1);
        update(
1, line[1]);
        
double res = 0;
        
for(i = 2; i < t; i++)
        {
            res 
+= segTree[1].cnt * (line[i].x - line[i - 1].x);
            update(
1, line[i]);
        }
        printf(
"Test case #%d\n", iCase);
        printf(
"Total explored area: %.2lf\n\n", res);
    }
    
return 0;
}
posted on 2011-10-25 23:52 LLawliet 閱讀(269) 評論(0)  編輯 收藏 引用 所屬分類: 線段樹
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            91久久久在线| 亚洲黄色在线| 久久精品久久综合| 国产一区二区三区在线观看网站| 久久精品99国产精品| 久久狠狠久久综合桃花| 亚洲国产片色| 一区二区三区www| 国产区亚洲区欧美区| 蜜臀91精品一区二区三区| 欧美v日韩v国产v| 亚洲摸下面视频| 久久精品国产96久久久香蕉| 亚洲精品美女久久久久| 在线性视频日韩欧美| 国产专区一区| 亚洲精品一区二区三区av| 国产精自产拍久久久久久| 欧美激情第一页xxx| 国产精品国产三级国产aⅴ无密码| 欧美一二三区精品| 欧美aⅴ99久久黑人专区| 亚洲中字在线| 欧美va日韩va| 久久久久综合网| 欧美色图一区二区三区| 久久亚洲免费| 欧美日韩中字| 欧美激情aⅴ一区二区三区| 国产精品视频福利| 亚洲国产精品福利| 国产欧美一区二区视频| 欧美激情女人20p| 国产日韩综合| 亚洲免费av电影| 亚洲国产精品久久久| 亚洲影视在线| 亚洲图中文字幕| 免费一级欧美在线大片| 欧美一区二区三区四区在线观看地址| 老巨人导航500精品| 久久国产精品亚洲77777| 欧美视频专区一二在线观看| 欧美国产大片| 在线日韩av片| 久久精品亚洲一区二区三区浴池 | 老色鬼久久亚洲一区二区 | 国内自拍一区| 亚洲一区在线直播| 99ri日韩精品视频| 欧美黄色成人网| 欧美风情在线观看| 亚洲国产精品va| 久久精品日韩| 麻豆91精品91久久久的内涵| 国产免费观看久久黄| 亚洲影音先锋| 欧美在线观看视频一区二区三区| 欧美日韩一区二区三区| 日韩午夜在线| 亚洲一级影院| 欧美三级视频在线观看| 99国产精品| 亚洲少妇中出一区| 国产精品video| 亚洲欧美国产三级| 久久精品国产免费观看| 国产性天天综合网| 久久久www成人免费无遮挡大片| 久久久亚洲国产天美传媒修理工 | 亚洲三级视频在线观看| 蜜臀av国产精品久久久久| 欧美成人午夜激情| 在线精品观看| 欧美精品一区二区视频 | 亚洲在线成人精品| 久久精品国产免费观看| 在线播放不卡| 欧美激情国产日韩| 亚洲一级电影| 美女久久一区| 一本色道久久99精品综合| 国产精品高清一区二区三区| 亚洲欧美日韩精品综合在线观看| 久久久国产一区二区三区| 亚洲电影免费观看高清完整版在线 | 一区二区欧美日韩| 国产精品久久国产三级国电话系列 | 宅男在线国产精品| 久久精品国产91精品亚洲| 国内精品久久久久影院优| 久久亚洲不卡| 日韩亚洲欧美中文三级| 久久精品日产第一区二区三区| 亚洲高清一区二| 国产精品大片wwwwww| 久久人人爽爽爽人久久久| 亚洲国产成人av好男人在线观看| av成人免费观看| 国产综合久久久久久| 欧美激情1区2区| 一本色道久久综合| 久久精品视频va| 一区二区欧美精品| 一区二区在线观看视频在线观看| 欧美日本在线| 欧美中文在线字幕| 亚洲乱码一区二区| 久久激情综合| 亚洲一区日韩| 在线成人免费视频| 国产精品永久免费| 欧美日韩午夜在线视频| 美女999久久久精品视频| 亚洲欧美精品中文字幕在线| 亚洲人成人一区二区在线观看| 久久久夜夜夜| 午夜亚洲伦理| 99视频在线观看一区三区| 激情小说另类小说亚洲欧美| 国产精品色婷婷| 欧美激情综合网| 美乳少妇欧美精品| 欧美影院在线播放| 午夜精品影院| 亚洲资源av| 亚洲午夜女主播在线直播| 亚洲区免费影片| 亚洲国产日韩一区| 亚洲高清视频在线观看| 欧美va天堂在线| 免费亚洲电影在线观看| 久久精品成人一区二区三区蜜臀 | 亚洲欧美经典视频| 亚洲一区二区在线播放| 日韩视频永久免费| 亚洲免费av电影| 日韩亚洲在线观看| 一本色道久久综合亚洲精品按摩 | 在线成人激情视频| 亚洲第一视频网站| 亚洲国产小视频在线观看| 亚洲国产精品123| 亚洲精品久久久久| 亚洲精选大片| 中文国产亚洲喷潮| 午夜精品在线看| 久久国产精品色婷婷| 久热成人在线视频| 欧美国产精品劲爆| 亚洲日本久久| 中文亚洲字幕| 午夜精品一区二区三区在线播放| 午夜精品久久久久久久久久久| 亚洲欧美国产制服动漫| 欧美怡红院视频| 麻豆精品91| 欧美午夜不卡在线观看免费 | 欧美精品色综合| 欧美性猛交一区二区三区精品| 国产精品久久午夜| 国产偷自视频区视频一区二区| 国产专区综合网| 亚洲激情专区| 亚洲自拍电影| 快she精品国产999| 亚洲精品免费电影| 香蕉成人久久| 免费成人美女女| 欧美四级在线观看| 国产亚洲人成网站在线观看| 1024国产精品| 亚洲自拍偷拍福利| 鲁大师影院一区二区三区| 亚洲精品乱码久久久久久按摩观| 亚洲午夜高清视频| 老色鬼精品视频在线观看播放| 国产精品草草| 在线观看日韩一区| 亚洲愉拍自拍另类高清精品| 巨乳诱惑日韩免费av| 日韩视频第一页| 久久综合图片| 国产精品久久久久久影院8一贰佰| 伊人精品成人久久综合软件| 日韩亚洲欧美一区| 麻豆精品在线观看| 亚洲午夜av在线| 欧美日本不卡| 136国产福利精品导航| 欧美亚洲网站| 亚洲青涩在线| 理论片一区二区在线| 国产日韩精品在线播放| 99精品视频免费全部在线| 麻豆免费精品视频| 欧美一级免费视频| 国产精品亚洲综合久久| 一本一本久久a久久精品牛牛影视| 久久综合久久久久88|