2 条题解

  • 0
    @ 2025-10-8 16:50:31
    #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
      @ 2025-10-8 16:50:12
      #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
      上传者