2 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N = 10; typedef long long LL; struct Line{double p,st,ed;int flg; }L[N];// 一条竖线:x坐标是p,y的范围是st至ed bool cmp(Line n1,Line n2){ return (n1.p!=n2.p) ? n1.p<n2.p : n1.flg>n2.flg;} double s[N]; struct trnode{int l,r,lc,rc,c;double len;}tr[N*2];int trlen; void bt(int l,int r) { int now=++trlen; tr[now]=trnode{l,r,-1,-1,0,0}; if(l+1<r) { int mid=(l+r)>>1; tr[now].lc=trlen+1;bt(l,mid); tr[now].rc=trlen+1;bt(mid,r); } } void change(int now,double l,double r,int c) { if(r<=s[tr[now].l] || s[tr[now].r]<=l) return ; int lc=tr[now].lc,rc=tr[now].rc; if(l<=s[tr[now].l] && s[tr[now].r]<=r)tr[now].c+=c; else change(lc,l,r,c),change(rc,l,r,c); if(tr[now].c) tr[now].len=s[tr[now].r]-s[tr[now].l]; else tr[now].len=(lc==-1)?0:tr[lc].len+tr[rc].len; } int main() { //freopen("a.in","r",stdin);freopen("a.out","w",stdout); int n=2; double sum=0; for(int i=1;i<=n;i++) { double X1,Y1,X2,Y2;scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2); if(X1>X2)swap(X1,X2); if(Y1>Y2)swap(Y1,Y2); sum+=fabs(X1-X2)*fabs(Y1-Y2); L[i] =Line{X1,Y1,Y2, 1}; L[n+i]=Line{X2,Y1,Y2,-1}; s[i]=Y1,s[n+i]=Y2; } n<<=1; double ans=0;int cnt; sort(s+1,s+n+1);cnt=unique(s+1,s+n+1)-(s+1); trlen=0;bt(1,cnt); sort(L+1,L+n+1,cmp); for(int i=1;i<n;i++) { change(1,L[i].st,L[i].ed,L[i].flg); ans+=(L[i+1].p-L[i].p)*tr[1].len; } printf("%.2lf\n",sum-ans); return 0; } -
0
#include<bits/stdc++.h> using namespace std; const int N = 10; typedef long long LL; struct Line{double p,st,ed;int flg; }L[N];// 一条竖线:x坐标是p,y的范围是st至ed bool cmp(Line n1,Line n2){ return (n1.p!=n2.p) ? n1.p<n2.p : n1.flg>n2.flg;} double s[N]; struct trnode{int l,r,lc,rc,c;double len;}tr[N*2];int trlen; void bt(int l,int r) { int now=++trlen; tr[now]=trnode{l,r,-1,-1,0,0}; if(l+1<r) { int mid=(l+r)>>1; tr[now].lc=trlen+1;bt(l,mid); tr[now].rc=trlen+1;bt(mid,r); } } void change(int now,double l,double r,int c) { if(r<=s[tr[now].l] || s[tr[now].r]<=l) return ; int lc=tr[now].lc,rc=tr[now].rc; if(l<=s[tr[now].l] && s[tr[now].r]<=r)tr[now].c+=c; else change(lc,l,r,c),change(rc,l,r,c); if(tr[now].c) tr[now].len=s[tr[now].r]-s[tr[now].l]; else tr[now].len=(lc==-1)?0:tr[lc].len+tr[rc].len; } int main() { //freopen("a.in","r",stdin);freopen("a.out","w",stdout); int n=2; double sum=0; for(int i=1;i<=n;i++) { double X1,Y1,X2,Y2;scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2); if(X1>X2)swap(X1,X2); if(Y1>Y2)swap(Y1,Y2); sum+=fabs(X1-X2)*fabs(Y1-Y2); L[i] =Line{X1,Y1,Y2, 1}; L[n+i]=Line{X2,Y1,Y2,-1}; s[i]=Y1,s[n+i]=Y2; } n<<=1; double ans=0;int cnt; sort(s+1,s+n+1);cnt=unique(s+1,s+n+1)-(s+1);//得到最后一个元素位置的下一位,减去第一个元素的位置 ,刚好是个数 // unique函数可以去除数组中相邻重复项,想要实现完全去重功能,需要在执行unique函数之前先对数组进行排序 trlen=0;bt(1,cnt); sort(L+1,L+n+1,cmp); for(int i=1;i<n;i++) { change(1,L[i].st,L[i].ed,L[i].flg); ans+=(L[i+1].p-L[i].p)*tr[1].len; } printf("%.2lf\n",sum-ans); return 0; }
- 1
信息
- ID
- 406
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 8
- 标签
- 递交数
- 12
- 已通过
- 8
- 上传者