#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<iomanip>
#include<stdlib.h>
#include<cstdio>
#include<string>
#include<map>
#include<string.h>
#include<set>
using namespace std;

typedef long long ll;
typedef  pair<int,int> P;
const int INF = 0x7fffffff;
const int MAX_N = 10000;
const int MAX_V = 0;
const int MAX_M = 0;

//Define array zone
int N, T;
double x[4*MAX_N], ty[4*MAX_N], ty1[4*MAX_N], val[4*MAX_N];
int data[4*MAX_N];
map<double, int> m;

//Cut-off rule
struct edge{
	int tcor, bcor;
	edge(){}
	edge(int tcor, int bcor):tcor(tcor), bcor(bcor){}
}y[4*MAX_N];

//establish segment tree

void init(int k, int l, int r){
	data[k] = 0;
	//leaf node
	if(r-l==1){
		val[k] = ty[l+1]-ty[l];
	}
	else{
		int chl = 2*k+1, chr = 2*k+2;
		init(chl, l, (l+r)/2);
		init(chr, (l+r)/2, r);
		val[k] = val[chl] + val[chr];
	}
}

//add edge to section a, b,      k is the index of the node,  
void add(int a, int b, int x, int k, int l, int r){
	if(a<=l&&r<=b) data[k] += x;
	else if(l<b&&a<r){
		add(a, b, x, k*2+1, l, (l+r)/2);
		add(a, b, x, k*2+2, (l+r)/2, r);
	}
}

double sum(int a, int b, int k, int l, int r){
	if(b<=l||a>=r) return 0;
	if(a<=l && r<= b){
		if(data[k]>0) return val[k];
		if(data[k]==0&&r-l==1) return 0;
		else return sum(a,b,2*k+1, l, (l+r)/2)
						+sum(a,b,2*k+2,(l+r)/2, r);
	}
	else{
		return sum(a,b,2*k+1, l, (l+r)/2)
				+sum(a,b,2*k+2,(l+r)/2, r);
	}
}

void solve(){
	vector<pair<double, int> > events;
	for(int i=0; i<2*N; i++){
		events.push_back(make_pair(x[i],i));
	}
	sort(events.begin(), events.begin()+2*N);

	//discretize
	sort(ty, ty+2*N);
	int num = unique(ty,ty+2*N)-ty;
	for(int i=0; i<num; i++)
		m[ty[i]] = i;


	//establish edges
	for(int i=0; i<N; i++){
		y[i] = edge( m[max(ty1[i],ty1[i+N])], m[min(ty1[i],ty1[i+N])] );
		y[i+N] = y[i];
	}

	//calculate
	double res = 0;
	init(0,0,num-1);
	int idx = events[0].second; double crtx = events[0].first; edge tempy = y[idx];
	add(tempy.bcor, tempy.tcor, idx<N?1:-1, 0, 0, num-1);
	for(int i=1; i<events.size(); i++){
		idx = events[i].second; edge tempy = y[idx];
		if(crtx<events[i].first){
			res += (events[i].first-crtx)*sum(0, num-1, 0, 0, num-1);
			crtx = events[i].first;
		}
		add(tempy.bcor, tempy.tcor, idx<N?1:-1, 0, 0, num-1);
	}
	cout<<"Test case #"<<++T<<endl;
	printf("Total explored area: %.2f\n\n", res);
}

int main(){
	while(cin>>N&&N!=0){
		for(int i=0; i<N; i++){
			cin>>x[i]>>ty[i]>>x[i+N]>>ty[i+N];
			ty1[i] = ty[i]; ty1[i+N] = ty[i+N];
		}
		solve();
	}
}

• Re:0ms过 纪念一下(写了4个小时调错无数的菜菜) (0) lew2018 2020-08-03 10:48:27