poj1151
https://blog.csdn.net/xianpingping/article/details/83032798
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define eps 1e-4 #define bug printf("********* ") #define debug(x) cout<<#x"=["<<x<<"]" <<endl typedef long long LL; typedef long long ll; const int maxn = 2e2 + 5; const int mod = 998244353; struct seg { double l,r,h; int d; seg(){} seg(double x1,double x2,double H,int c) : l(x1),r(x2),h(H),d(c){} bool operator < (const seg &a) const { return h < a.h; } }line[maxn << 2]; double Hash[maxn << 2]; double sum[maxn << 2]; int cnt[maxn << 2]; void init() { memset(cnt, 0, sizeof cnt); memset(sum, 0, sizeof sum); } void pushup(int o,int l,int r) { if(cnt[o]) sum[o] = Hash[r + 1] - Hash[l]; else sum[o] = sum[o << 1] + sum[o << 1 | 1]; } void update(int o,int l,int r,int ql,int qr,int v) { if(ql <= l && qr >= r) { cnt[o] += v; pushup(o,l,r); return; } int mid = (l + r) >> 1; if(ql <= mid) update(o << 1,l,mid,ql,qr,v); if(qr > mid) update(o << 1 | 1,mid + 1,r,ql,qr,v); pushup(o,l,r); } int main() { int n,_ =0; while(scanf("%d",&n) && n) { init(); double x1,x2,y1,y2; int cnt1 = 0,cnt2 = 0; for(int i = 1; i <= n; ++i) { scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); Hash[++cnt1] = x1; Hash[++cnt1] = x2; line[++cnt2] = seg(x1,x2,y1,1); line[++cnt2] = seg(x1,x2,y2,-1); } sort(Hash + 1, Hash + cnt1 + 1); sort(line + 1, line + cnt2 + 1); int k = unique(Hash + 1,Hash + 1 + cnt1) - Hash - 1; double ans = 0.0; for(int i = 1; i < cnt2; i++) { int l = lower_bound(Hash + 1,Hash + 1 + k,line[i].l) - Hash; int r = lower_bound(Hash + 1,Hash + 1 + k,line[i].r) - Hash - 1; if(l <= r) update(1,1,k - 1,l,r,line[i].d); ans += sum[1] * (line[i + 1].h - line[i].h); } printf("Test case #%d Total explored area: %.2f ",++_,ans); } }