• <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>

            superman

            聚精會(huì)神搞建設(shè) 一心一意謀發(fā)展
            posts - 190, comments - 17, trackbacks - 0, articles - 0
               :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

            ZOJ 1128 - Atlantis

            Posted on 2008-03-13 21:05 superman 閱讀(386) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ZOJ
              1 /* Accepted 1128 C++ 00:00.02 848K */
              2 #include <stdio.h>
              3 #include <iostream>
              4 
              5 using namespace std;
              6 
              7 template <typename T>
              8 class queue
              9 {
             10 private:
             11     int len;
             12     struct node
             13     {
             14         T item;
             15         node *next;
             16     }*front, *rear;
             17 public:
             18     queue()
             19     {
             20         len = 0;
             21         front = rear = NULL;
             22     }
             23     int size()
             24     {
             25         return len;
             26     }
             27     bool empty()
             28     {
             29         return len == 0;
             30     }
             31     void push(const T & item)
             32     {
             33         node *= new node;
             34         p -> item = item;
             35         p -> next = NULL;
             36         if(empty())
             37             front = rear = p;
             38         else
             39         {
             40             rear -> next = p;
             41             rear = p;
             42         }
             43         len++;
             44     }
             45     void pop(T & item)
             46     {
             47         node *= front;
             48         if(len == 1)
             49             front = rear = NULL;
             50         else
             51             front = front -> next;
             52         item = p -> item;
             53         delete p;
             54         len--;
             55     }
             56 };
             57 
             58 struct Rect
             59 {
             60     double x1, y1, x2, y2;
             61 };
             62 
             63 queue<Rect> rects;
             64 
             65 inline void addRect(double x1, double y1, double x2, double y2)
             66 {
             67     Rect tmp = {x1, y1, x2, y2};
             68     rects.push(tmp);
             69 }
             70 
             71 int main()
             72 {
             73     //freopen("p1128.in", "r", stdin);
             74     
             75     cout.setf(ios_base::showpoint);
             76     cout.setf(ios_base::fixed);
             77     cout.precision(2);
             78     
             79     int n, m = 1;
             80     double x1, y1, x2, y2;
             81     while((cin >> n) && n)
             82     {
             83         cin >> x1 >> y1 >> x2 >> y2;
             84         
             85         addRect(x1, y1, x2, y2);
             86         
             87         Rect tmp;
             88         for(int i = 2; i <= n; i++)
             89         {
             90             cin >> x1 >> y1 >> x2 >> y2;
             91             
             92             int k = rects.size();
             93             while(k--)
             94             {
             95                 rects.pop(tmp);
             96                 
             97                 if(x1 > tmp.x2 || x2 < tmp.x1 || y1 > tmp.y2 || y2 < tmp.y1)
             98                 {
             99                     rects.push(tmp);
            100                     continue;
            101                 }
            102                 
            103                 if(x1 >= tmp.x1 && x2 <= tmp.x2 && y1 >= tmp.y1 && y2 <= tmp.y2)
            104                     continue;
            105                 
            106                 if(x1 > tmp.x1)
            107                 {
            108                     addRect(tmp.x1, tmp.y1 , x1, tmp.y2);
            109                     tmp.x1 = x1;
            110                 }
            111                 if(x2 < tmp.x2)
            112                 {
            113                     addRect(x2, tmp.y1, tmp.x2, tmp.y2);
            114                     tmp.x2 = x2;
            115                 }
            116                 if(y1 > tmp.y1)
            117                     addRect(tmp.x1, tmp.y1, tmp.x2, y1);
            118                 if(y2 < tmp.y2)
            119                     addRect(tmp.x1, y2, tmp.x2, tmp.y2);
            120             }
            121             addRect(x1, y1, x2, y2);
            122         }
            123         double ans = 0.00000000;
            124         while(rects.empty() == false)
            125         {
            126             rects.pop(tmp);
            127             ans += (tmp.x2 - tmp.x1) * (tmp.y2 - tmp.y1);
            128         }
            129         cout << "Test case #" << m++ << endl;
            130         cout << "Total explored area: ";
            131         cout << ans << endl;
            132         cout << endl;
            133     }
            134     
            135     return 0;
            136 }
            137 
            一本一本久久A久久综合精品| 国产91久久精品一区二区| 国产亚洲成人久久| 无夜精品久久久久久| 色综合久久久久无码专区| 99久久国产主播综合精品| 欧美精品九九99久久在观看| 激情伊人五月天久久综合| 欧美久久一区二区三区| 国产午夜精品久久久久免费视 | 久久人妻AV中文字幕| 久久99国产综合精品| 大香伊人久久精品一区二区| 国产精品久久久久久影院| 一本久久综合亚洲鲁鲁五月天| 狠狠色丁香久久综合五月| 久久精品无码一区二区WWW| 久久99精品久久久久久齐齐| 久久国产热精品波多野结衣AV| 亚洲国产小视频精品久久久三级| 久久福利青草精品资源站| 亚洲精品乱码久久久久久| 欧美亚洲国产精品久久久久| 国产高清国内精品福利99久久| 久久精品国产亚洲av麻豆色欲| 日韩十八禁一区二区久久| 99久久成人18免费网站| 国产91色综合久久免费分享| 日韩人妻无码一区二区三区久久| 亚洲精品国产第一综合99久久| 久久青青草原综合伊人| 久久国产精品一国产精品金尊| 性欧美大战久久久久久久久| 无码人妻久久一区二区三区蜜桃| 久久AⅤ人妻少妇嫩草影院| 9999国产精品欧美久久久久久| 麻豆精品久久精品色综合| 久久亚洲综合色一区二区三区| 久久九九亚洲精品| 精品久久综合1区2区3区激情| 精品久久久久久久中文字幕|