Posted on 2008-03-13 21:05
superman 閱讀(383)
評論(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 *p = 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 *p = 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