2 条题解

  • 0
    @ 2025-10-8 16:56:29
    #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
      @ 2025-10-8 16:56:17
      #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

      C15_2*【扫描线】亚特兰蒂斯[POJ1151]

      信息

      ID
      1330
      时间
      4000ms
      内存
      128MiB
      难度
      7
      标签
      递交数
      160
      已通过
      37
      上传者