题目地址
一直WA 一个一个字符比对正确代码，想吐槽的是 答案输出只能%f ！！！ woc
还有犯了一些小错误 比如坐标值y用int保存了
从左到右每个x值，把y的坐标分为n-1个区间，那么就转化为线段树了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100+5;
struct CLine{double x,y1,y2;bool bleft;CLine(double x=0,double y1=0,double y2=0,bool bl=false):x(x),y1(y1),y2(y2),bleft(bl) {}bool operator < (const CLine& l) const {return x < l.x;}
}line[maxn*2];
struct CNode{int L,R;CNode *pLeft,*pRight;double Len;int Covered; //被 完全覆盖 了几层 CNode(int l=0,int r=0,double len=0,int c=0,CNode *pl=NULL,CNode *pr=NULL):L(l),R(r),Len(len),Covered(c),pLeft(pl),pRight(pr){}int Mid(){ return (L+R)/2; }
}tree[maxn*10];
double y[maxn*2];
int nNode;
void BuildTree(CNode *root,int s,int e)
{*root=CNode(s,e,0,0);if(s==e) return;root->pLeft=++nNode+tree;root->pRight=++nNode+tree;int mid=root->Mid();BuildTree(root->pLeft,s,mid);BuildTree(root->pRight,mid+1,e);
}
void Add(CNode *root,int s,int e)
{if(root->L==s&&root->R==e){root->Len=y[e+1]-y[s]; //长度就为该区间长度 root->Covered++; return;}int mid=root->Mid();if(e<=mid) Add(root->pLeft,s,e);else if(s>mid) Add(root->pRight,s,e);else {Add(root->pLeft,s,mid);Add(root->pRight,mid+1,e);}if(root->Covered==0) root->Len=root->pLeft->Len+root->pRight->Len;
}
void Delete(CNode *root,int s,int e)
{if(root->L==s&&root->R==e){root->Covered--;if(root->Covered==0){if(s==e) root->Len=0; //只有一个区间Covered=0时不可能被还存在矩形 else root->Len=root->pRight->Len+root->pLeft->Len;}return;}int mid=root->Mid();if(e<=mid) Delete(root->pLeft,s,e);else if(s>mid) Delete(root->pRight,s,e);else {Delete(root->pLeft,s,mid);Delete(root->pRight,mid+1,e);}if(root->Covered==0) root->Len=root->pLeft->Len+root->pRight->Len;
}
int main()
{int N,ycnt,nline,kase=0;double x1,x2,y1,y2;for(;;){scanf("%d",&N);if(!N) break;ycnt=nline=0;for(int i=0;i<N;i++){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);y[ycnt++]=y1; y[ycnt++]=y2;line[nline++]=CLine(x1,y1,y2,true);line[nline++]=CLine(x2,y1,y2,false);}sort(y,y+ycnt);ycnt=unique(y,y+ycnt)-y;nNode=0; BuildTree(tree,0,ycnt-1-1);sort(line,line+nline);double ans=0;for(int i=0;i<nline-1;i++){int L=find(y,y+ycnt,line[i].y1)-y;int R=find(y,y+ycnt,line[i].y2)-y;if(line[i].bleft) Add(tree,L,R-1); //y1,y2 两点之间正好是[L,R-1]区间 else Delete(tree,L,R-1);ans+=tree[0].Len*(line[i+1].x-line[i].x);}printf("Test case #%d\nTotal explored area: %.2f \n\n",++kase,ans);}return 0;
}