{"id":290,"date":"2012-11-30T16:13:00","date_gmt":"2012-11-30T08:13:00","guid":{"rendered":"http:\/\/nike0good.jp1.rpvhost.net\/195"},"modified":"2012-11-30T16:13:00","modified_gmt":"2012-11-30T08:13:00","slug":"and_poj_1151_rectangular_area","status":"publish","type":"post","link":"https:\/\/nike0good.com\/?p=290","title":{"rendered":"POJ 1151(\u77e9\u5f62\u9762\u79ef\u5e76\uff09"},"content":{"rendered":"\n\n\n
\n
Language:\n\n\n\n
Time Limit:<\/strong> 1000MS<\/td>\n <\/td>\nMemory Limit:<\/strong> 10000K<\/td>\n<\/tr>\n
Total Submissions:<\/strong> 13134<\/td>\n <\/td>\nAccepted:<\/strong> 5050<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n

Description<\/p>\n

\nThere 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
\n total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.<\/div>\n

Input<\/p>\n

\nThe input 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 contains four numbers x1;y1;x2;y2 (0 <= x1 < x2 <=
\n 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. 
\nThe input file is terminated by a line containing a single 0. Don't process it.<\/div>\n

Output<\/p>\n

\nFor each test case, your program should output one section. The first line of each section must be "Test case #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
\n (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. 
\nOutput a blank line after each test case.<\/div>\n

Sample Input<\/p>\n

2\n10 10 20 20\n15 15 25 25.5\n0<\/pre>\n
Sample Output<\/p>\n
Test case #1\nTotal explored area: 180.00 <\/pre>\n
Source<\/p>\n
\nMid-Central European Regional Contest 2000<\/a><\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
<\/p>\n
\u540cHdu 1542<\/a>\uff0c\u4e0d\u8fc7\u6570\u636e\u53d8\u6c34\u2026\u2026<\/span><\/p>\n

\n<\/span><\/p>\n
<\/span><\/p>\n
#include<cstdio>\n#include<cstring>\n#include<cstdlib>\n#include<cmath>\n#include<cctype>\n#include<iostream>\n#include<functional>\n#include<algorithm>\n#include<map>\nusing namespace std;\n#define MAXN (2000+10)\n#define MAXT (1000*2*10)\n#define Lson (x<<1)\n#define Rson ((x<<1)^1)\nint tt,n,size;\ndouble x[MAXN];\nstruct SegMent\n{\n    double x1,x2,h;\n    int type;\n    SegMent(){}\n    SegMent(double _x1,double _x2,double _h,int _type):x1(_x1),x2(_x2),h(_h),type(_type){}\n    friend bool operator<(const SegMent a,const SegMent b){return a.h<b.h;    }\n}a[MAXN];\nmap<double , int>  hpos;\ndouble len[MAXT];\nstruct SegMentTree\n{\n    int n,M,cnt[MAXT];\n    double sum[MAXT];\n    int mark[MAXT];\n    void fillchar(int _n)\n    {\n        n=_n;\n        memset(cnt,0,sizeof(cnt));\n        memset(sum,0,sizeof(sum));\n        memset(mark,0,sizeof(mark));\n        M=1;while (M-2<n) M<<=1;\n        x[0]=0;memset(len,0.0,sizeof(len));\n        for (int i=M+1;i<=M+size;i++) len[i]=x[i-M]-x[i-M-1];\n        for (int i=M-1;i>0;i--) len[i]=len[i<<1]+len[(i<<1)^1];\n    }\n    void pushup(int x)\n    {\n        sum[x]=cnt[x]?len[x]:(x>=M?0:sum[Lson]+sum[Rson]);\n    }\n    void update(int x)\n    {\n        for (;x;x>>=1)\n        {\n            pushup(x);\n        }\n    }\n\n    void insert(int l,int r,int c)\n    {\n        int ll=l-1+M,rr=r+1+M;\n        for (l=l-1+M,r=r+1+M;l^r^1;l>>=1,r>>=1)\n        {\n            if (~l&1) {cnt[l+1]+=c;pushup(l+1);} \/*\u6539\u53d8sum\u7684\u503c *\/\n            if (r&1) {cnt[r-1]+=c;pushup(r-1);}\n        }\n        update(ll);update(rr);\n    }\n}t;\n\nint main()\n{\n\/\/    freopen("Hdu1542.in","r",stdin);\n    tt=0;\n    while (scanf("%d",&n)!=EOF)\n    {\n        tt++;\n        if (!n) break;\n        for (int i=1;i<=2*n;i+=2)\n        {\n\t\t\tdouble x1,y1,x2,y2;\n            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);\n            x[i]=x1;x[i+1]=x2;\n            a[i]=SegMent(x1,x2,y1,1);\n            a[i+1]=SegMent(x1,x2,y2,-1);\n        }\n\n        sort(a+1,a+2*n+1);\n        sort(x+1,x+2*n+1);\n        size=unique(x+1,x+2*n+1)-(x+1);\n        for (int i=1;i<=size;i++) hpos[x[i]]=i;\n        t.fillchar(size);\n\n\n        double ans=0;a[0].h=a[1].h;\n        for (int i=1;i<=2*n;i++)\n        {\n            ans+=(a[i].h-a[i-1].h)*t.sum[1];\n            t.insert(hpos[a[i].x1]+1,hpos[a[i].x2],a[i].type);\n        }\n        printf("Test case #%dnTotal explored area: %.2lfnn",tt,ans);\n\n\n    }\n    return 0;\n}<\/pre>\n<\/p>\n
\n<\/p>\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Language: Default Atlantis Time Limit: 1000MS &nbs […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_coblocks_attr":"","_coblocks_dimensions":"","_coblocks_responsive_height":"","_coblocks_accordion_ie_support":"","footnotes":""},"categories":[3],"tags":[77],"class_list":["post-290","post","type-post","status-publish","format-standard","hentry","category-defaultcategory","tag-scan_line"],"yoast_head":"\nPOJ 1151(\u77e9\u5f62\u9762\u79ef\u5e76\uff09 - nike0good<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/nike0good.com\/?p=290\" \/>\n<meta property=\"og:locale\" content=\"zh_CN\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"POJ 1151(\u77e9\u5f62\u9762\u79ef\u5e76\uff09 - nike0good\" \/>\n<meta property=\"og:description\" content=\"Language: Default Atlantis Time Limit: 1000MS &nbs […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/nike0good.com\/?p=290\" \/>\n<meta property=\"og:site_name\" content=\"nike0good\" \/>\n<meta property=\"article:published_time\" content=\"2012-11-30T08:13:00+00:00\" \/>\n<meta name=\"author\" content=\"nike0good\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u4f5c\u8005\" \/>\n\t<meta name=\"twitter:data1\" content=\"nike0good\" \/>\n\t<meta name=\"twitter:label2\" content=\"\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 \u5206\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=290#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=290\"},\"author\":{\"name\":\"nike0good\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/#\\\/schema\\\/person\\\/4defa38da89de87e400861e73396baad\"},\"headline\":\"POJ 1151(\u77e9\u5f62\u9762\u79ef\u5e76\uff09\",\"datePublished\":\"2012-11-30T08:13:00+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=290\"},\"wordCount\":271,\"commentCount\":0,\"keywords\":[\"\u626b\u63cf\u7ebf\"],\"articleSection\":[\"DefaultCategory\"],\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/nike0good.com\\\/?p=290#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=290\",\"url\":\"https:\\\/\\\/nike0good.com\\\/?p=290\",\"name\":\"POJ 1151(\u77e9\u5f62\u9762\u79ef\u5e76\uff09 - nike0good\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/#website\"},\"datePublished\":\"2012-11-30T08:13:00+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/#\\\/schema\\\/person\\\/4defa38da89de87e400861e73396baad\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=290#breadcrumb\"},\"inLanguage\":\"zh-Hans\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/nike0good.com\\\/?p=290\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/?p=290#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/nike0good.com\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"POJ 1151(\u77e9\u5f62\u9762\u79ef\u5e76\uff09\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/#website\",\"url\":\"https:\\\/\\\/nike0good.com\\\/\",\"name\":\"nike0good\",\"description\":\"\u6709\u6240\u4f5c\u4e3a\u662f\u4eba\u751f\u7684\u6700\u9ad8\u5883\u754c\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/nike0good.com\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"zh-Hans\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/nike0good.com\\\/#\\\/schema\\\/person\\\/4defa38da89de87e400861e73396baad\",\"name\":\"nike0good\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"zh-Hans\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g\",\"caption\":\"nike0good\"},\"sameAs\":[\"https:\\\/\\\/nike0good.com\"],\"url\":\"https:\\\/\\\/nike0good.com\\\/?author=1\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"POJ 1151(\u77e9\u5f62\u9762\u79ef\u5e76\uff09 - nike0good","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/nike0good.com\/?p=290","og_locale":"zh_CN","og_type":"article","og_title":"POJ 1151(\u77e9\u5f62\u9762\u79ef\u5e76\uff09 - nike0good","og_description":"Language: Default Atlantis Time Limit: 1000MS &nbs […]","og_url":"https:\/\/nike0good.com\/?p=290","og_site_name":"nike0good","article_published_time":"2012-11-30T08:13:00+00:00","author":"nike0good","twitter_card":"summary_large_image","twitter_misc":{"\u4f5c\u8005":"nike0good","\u9884\u8ba1\u9605\u8bfb\u65f6\u95f4":"3 \u5206"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/nike0good.com\/?p=290#article","isPartOf":{"@id":"https:\/\/nike0good.com\/?p=290"},"author":{"name":"nike0good","@id":"https:\/\/nike0good.com\/#\/schema\/person\/4defa38da89de87e400861e73396baad"},"headline":"POJ 1151(\u77e9\u5f62\u9762\u79ef\u5e76\uff09","datePublished":"2012-11-30T08:13:00+00:00","mainEntityOfPage":{"@id":"https:\/\/nike0good.com\/?p=290"},"wordCount":271,"commentCount":0,"keywords":["\u626b\u63cf\u7ebf"],"articleSection":["DefaultCategory"],"inLanguage":"zh-Hans","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/nike0good.com\/?p=290#respond"]}]},{"@type":"WebPage","@id":"https:\/\/nike0good.com\/?p=290","url":"https:\/\/nike0good.com\/?p=290","name":"POJ 1151(\u77e9\u5f62\u9762\u79ef\u5e76\uff09 - nike0good","isPartOf":{"@id":"https:\/\/nike0good.com\/#website"},"datePublished":"2012-11-30T08:13:00+00:00","author":{"@id":"https:\/\/nike0good.com\/#\/schema\/person\/4defa38da89de87e400861e73396baad"},"breadcrumb":{"@id":"https:\/\/nike0good.com\/?p=290#breadcrumb"},"inLanguage":"zh-Hans","potentialAction":[{"@type":"ReadAction","target":["https:\/\/nike0good.com\/?p=290"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/nike0good.com\/?p=290#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/nike0good.com\/"},{"@type":"ListItem","position":2,"name":"POJ 1151(\u77e9\u5f62\u9762\u79ef\u5e76\uff09"}]},{"@type":"WebSite","@id":"https:\/\/nike0good.com\/#website","url":"https:\/\/nike0good.com\/","name":"nike0good","description":"\u6709\u6240\u4f5c\u4e3a\u662f\u4eba\u751f\u7684\u6700\u9ad8\u5883\u754c","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/nike0good.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"zh-Hans"},{"@type":"Person","@id":"https:\/\/nike0good.com\/#\/schema\/person\/4defa38da89de87e400861e73396baad","name":"nike0good","image":{"@type":"ImageObject","inLanguage":"zh-Hans","@id":"https:\/\/secure.gravatar.com\/avatar\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/8e5fa08d5c367a1a6fb5ff13bb10ed5a331f981513256951290ae42322da6854?s=96&d=identicon&r=g","caption":"nike0good"},"sameAs":["https:\/\/nike0good.com"],"url":"https:\/\/nike0good.com\/?author=1"}]}},"_links":{"self":[{"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/posts\/290","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nike0good.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=290"}],"version-history":[{"count":0,"href":"https:\/\/nike0good.com\/index.php?rest_route=\/wp\/v2\/posts\/290\/revisions"}],"wp:attachment":[{"href":"https:\/\/nike0good.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=290"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nike0good.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=290"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nike0good.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=290"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}