2 条题解
-
0
#include<bits/stdc++.h> #define lc (p<<1) #define rc (p<<1|1) #define mid ((tr[p].l+tr[p].r)>>1) #define eps 1e-6 using namespace std; const int N=210; struct Line{double p, st, ed;int flg; }L[N]; bool cmp(Line n1,Line n2){return n1.p<n2.p;} double lsh[N]; struct trnode{int l, r, c;double len;}tr[N<<3]; void bt(int p, int l, int r) { tr[p]=trnode{l, r, 0, 0.0}; if(l+1==r)return ; bt(lc, l, mid); bt(rc, mid, r); } void change(int p, double l, double r, int c) { if(r<=lsh[tr[p].l]+eps || lsh[tr[p].r]<=l+eps)return; if(l<=lsh[tr[p].l]+eps && lsh[tr[p].r]<=r+eps)tr[p].c+=c; else change(lc, l, r, c),change(rc, l, r, c); tr[p].len= tr[p].c>0? (lsh[tr[p].r]-lsh[tr[p].l]) : (tr[lc].len+tr[rc].len) ; } int main() { int n, T=0; while( scanf("%d",&n)!=EOF&&n) { memset(tr,0,sizeof(tr)); for(int i=1;i<=n;i++) { double X1, Y1, X2, Y2;scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2); L[i] =Line{X1, Y1, Y2, 1}; L[n+i]=Line{X2, Y1, Y2, -1}; lsh[i]=Y1;lsh[n+i]=Y2; } double ans=0; sort(lsh+1,lsh+2*n+1);int ln=unique(lsh+1,lsh+2*n+1)-lsh-1; bt(1,1,ln); sort(L+1,L+2*n+1,cmp); for(int i=1;i<2*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("Test case #%d\n",++T); printf("Total explored area: %.2lf\n\n",ans); } return 0; } -
0
#include<bits/stdc++.h> #define lc (p<<1) #define rc (p<<1|1) #define mid ((tr[p].l+tr[p].r)>>1) #define eps 1e-6 using namespace std; const int N=210; struct Line{double p,st,ed;int flg; }L[N]; bool cmp(Line n1,Line n2){return n1.p<n2.p;} double lsh[N]; struct trnode{int l,r,c;double len;}tr[N<<3]; void bt(int p,int l,int r) { tr[p]=trnode{l,r,0,0.0}; if(l+1==r)return ; bt(lc,l,mid); bt(rc,mid,r); } void change(int p,double l,double r,int c) { if(r<=lsh[tr[p].l]+eps || lsh[tr[p].r]<=l+eps)return; if(l<=lsh[tr[p].l]+eps && lsh[tr[p].r]<=r+eps)tr[p].c+=c; else change(lc,l,r,c),change(rc,l,r,c); tr[p].len= tr[p].c>0? (lsh[tr[p].r]-lsh[tr[p].l]) : (tr[lc].len+tr[rc].len) ; } int main() { int n,T=0; while( scanf("%d",&n)!=EOF&&n) { memset(tr,0,sizeof(tr)); for(int i=1;i<=n;i++) { double X1,Y1,X2,Y2;scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2); L[i] =Line{X1,Y1,Y2, 1}; L[n+i]=Line{X2,Y1,Y2,-1}; lsh[i]=Y1,lsh[n+i]=Y2; } double ans=0; sort(lsh+1,lsh+2*n+1);int ln=unique(lsh+1,lsh+2*n+1)-lsh-1; bt(1,1,ln); sort(L+1,L+2*n+1,cmp); for(int i=1;i<2*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("Test case #%d\n",++T); printf("Total explored area: %.2lf\n\n",ans); } return 0; }
- 1
信息
- ID
- 1330
- 时间
- 4000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 160
- 已通过
- 37
- 上传者