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

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>
            日韩一级黄色av| 欧美成年人网站| 亚洲视频精选在线| 国产精品白丝jk黑袜喷水| 亚洲一区二区三区视频| 午夜精品成人在线| 激情小说另类小说亚洲欧美| 狂野欧美激情性xxxx欧美| 蜜臀av性久久久久蜜臀aⅴ四虎 | 另类综合日韩欧美亚洲| ●精品国产综合乱码久久久久| 久久成人精品视频| 欧美一二区视频| 黑人巨大精品欧美黑白配亚洲| 老司机免费视频久久| 欧美黑人多人双交| 久久9热精品视频| 噜噜噜噜噜久久久久久91| 亚洲网在线观看| 久久精品理论片| 亚洲主播在线| 久久久综合激的五月天| 99精品欧美一区二区蜜桃免费| 亚洲性线免费观看视频成熟| 极品av少妇一区二区| 一本色道久久综合狠狠躁篇的优点| 国产伦精品一区二区三区免费迷 | 亚洲欧洲日本mm| 欧美视频免费在线观看| 免费在线观看精品| 国产精品乱码妇女bbbb| 亚洲国产天堂久久国产91| 国产区在线观看成人精品| 欧美国产激情二区三区| 国产日韩精品久久久| 日韩视频免费大全中文字幕| 狠狠色综合日日| 亚洲理论电影网| 亚洲国产成人av在线| 羞羞答答国产精品www一本 | 国产精品无码永久免费888| 亚洲二区在线观看| 国产原创一区二区| 亚洲一本视频| 亚洲一区尤物| 欧美日韩一区二区三区在线| 亚洲国产精品一区二区www在线| 国产主播在线一区| 中日韩美女免费视频网址在线观看 | 男人的天堂亚洲在线| 久久这里只有| 国内精品视频久久| 亚洲欧美日韩另类精品一区二区三区| 在线亚洲自拍| 欧美日韩国产综合新一区| 亚洲国产精品尤物yw在线观看| 国产一区二区三区在线免费观看| 亚洲一区二区三区精品在线| 亚洲欧美在线一区| 国产精品久久久一本精品| 亚洲三级网站| 在线亚洲精品| 国产精品白丝jk黑袜喷水| av成人手机在线| 夜夜嗨av一区二区三区| 欧美激情第五页| 亚洲日本无吗高清不卡| 亚洲裸体在线观看| 欧美高清在线视频观看不卡| 欧美激情综合| 亚洲精品一区二区三区四区高清| 巨乳诱惑日韩免费av| 亚洲电影免费观看高清完整版在线观看 | 在线亚洲一区观看| 亚洲欧美日韩一区二区三区在线观看| 欧美性事在线| 亚洲一区二区三区高清 | 亚洲精品在线一区二区| 亚洲特色特黄| 国产精品影院在线观看| 久久国产日韩| 亚洲电影第三页| 亚洲一区二区伦理| 国产一区白浆| 欧美高清在线播放| 亚洲女女女同性video| 久久久噜噜噜久久人人看| 亚洲国产导航| 国产精品亚洲人在线观看| 久久国产精品久久久久久久久久| 免费欧美网站| 亚洲欧美日韩另类| 在线免费观看日本一区| 欧美日本免费| 新67194成人永久网站| 欧美电影资源| 午夜欧美精品| 激情久久久久久久久久久久久久久久| 久久手机免费观看| 中日韩视频在线观看| 欧美在线啊v一区| 日韩一本二本av| 国产综合一区二区| 欧美日韩国产一级| 久久久久久久综合狠狠综合| 日韩视频在线永久播放| 久久国产精品色婷婷| 亚洲第一页自拍| 国产日韩av一区二区| 欧美成人国产一区二区| 亚洲午夜av在线| 理论片一区二区在线| 午夜激情一区| 亚洲小视频在线| 91久久在线| 在线观看久久av| 国产一区高清视频| 国产精品一级久久久| 欧美日韩1区2区3区| 欧美a级片一区| 久久精品青青大伊人av| 亚洲欧美日韩在线不卡| 妖精视频成人观看www| 欧美激情中文不卡| 久久午夜激情| 久久久久久一区二区三区| 亚洲欧美第一页| 亚洲一区二区av电影| a4yy欧美一区二区三区| 亚洲人www| 亚洲黄色精品| 91久久线看在观草草青青| 在线播放视频一区| …久久精品99久久香蕉国产| 狠狠色伊人亚洲综合网站色| 国产一区自拍视频| 国产一级久久| 在线观看亚洲一区| 1000精品久久久久久久久| 在线欧美一区| 亚洲精品日韩激情在线电影| 91久久久久久久久| 日韩午夜中文字幕| 99视频一区二区三区| 99精品国产高清一区二区| 日韩一级免费| 亚洲桃色在线一区| 欧美在线免费视屏| 久久久久久久波多野高潮日日| 久久精品国产久精国产思思| 久久久久久久综合| 女主播福利一区| 亚洲福利免费| 一本在线高清不卡dvd| 亚洲男人的天堂在线| 欧美一区二区视频在线观看| 久久久一区二区三区| 欧美母乳在线| 国产精品素人视频| 激情久久影院| 日韩视频在线观看一区二区| 亚洲网站在线观看| 久久久九九九九| 91久久黄色| 亚洲欧美国产精品va在线观看| 欧美一区激情| 欧美日本一区二区三区| 国产精品裸体一区二区三区| 国产一区二区三区在线观看精品| 亚洲高清一区二| 午夜精品福利电影| 欧美激情精品久久久久久| 亚洲免费播放| 久久免费一区| 国产精品激情电影| 亚洲第一精品久久忘忧草社区| 夜夜狂射影院欧美极品| 久久精品一本| 亚洲最黄网站| 久久综合给合久久狠狠色| 国产精品久久激情| 亚洲国产美女久久久久| 亚洲一区二区三区777| 欧美成人首页| 在线一区二区日韩| 另类酷文…触手系列精品集v1小说| 欧美欧美午夜aⅴ在线观看| 狠狠综合久久| 午夜精品偷拍| 91久久精品国产| 欧美在线亚洲一区| 美女脱光内衣内裤视频久久网站| 国产精品久久毛片a| aa级大片欧美| 欧美激情精品久久久久久免费印度 | 性色av香蕉一区二区| 欧美喷潮久久久xxxxx| 一区二区三区在线免费视频| 西西人体一区二区| 在线亚洲自拍|