比赛 2025.3.6 评测结果 WWWWW
题目名称 矩形周长 最终得分 0
用户昵称 djyqjy 运行时间 0.028 s
代码语言 C++ 内存使用 3.64 MiB
提交时间 2025-03-06 21:51:01
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
inline int re()
{
	int f=1,num=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
	return num*f;
}
const int N=5010,M=20010,eps=10001;
struct rec
{
	int x1,y1,x2,y2;
}rs[N];
struct line
{
	int x1,x2,y1,op;
}ls[N*2];
int n,m;
int x[2*N],t[2*N];
bool cmp(line a,line b)
{
	if(a.y1==b.y1) return a.op<b.op;
	return a.y1<b.y1;
}
int cha(int val)
{
	int l=1,r=m,mid;
	while(l<r)
	{
		mid=(l+r)/2;
		if(x[mid]>=val) r=mid;
		else l=mid+1;
	}
	return l;
}
vector<pair<int,int> >vec;
int ans;
int main()
{
	freopen("picture.in","r",stdin);
	freopen("picture.out","w",stdout);
	n=re();
	for(int i=1;i<=n;i++)
	{
		rs[i].x1=re()+eps,rs[i].y1=re()+eps,rs[i].x2=re()+eps,rs[i].y2=re()+eps;
		ls[2*i-1]=(line){rs[i].x1,rs[i].x2,rs[i].y1,1};
		ls[2*i]=(line){rs[i].x1,rs[i].x2,rs[i].y2,-1};
		x[2*i-1]=rs[i].x1,x[2*i]=rs[i].x2;
	}
	sort(x+1,x+1+2*n);
	m=unique(x+1,x+1+2*n)-(x+1);
	sort(ls+1,ls+1+2*n,cmp);
	int ll,r;
	for(int i=1;i<=2*n;i++)
	{
//		cout<<ls[i].x1<<' '<<ls[i].x2<<endl;
		ls[i].x1=cha(ls[i].x1);ls[i].x2=cha(ls[i].x2);
		for(int j=ls[i].x1;j<ls[i].x2;j++)
		{
			if(ls[i].op==1){t[j]++;if(t[j]==1) ans+=x[j+1]-x[j],vec.push_back(make_pair(x[j],x[j+1]));}
			else{t[j]--;if(t[j]==0) ans+=x[j+1]-x[j],vec.push_back(make_pair(x[j],x[j+1]));}
		}
		if(ls[i].y1!=ls[i+1].y1&&i!=2*n)
		{
//			for(int j=1;j<m;j++) if(!t[j]) vec.push_back(make_pair(x[j],x[j+1]));
			ll=r=0;sort(vec.begin(),vec.end());
			for(auto z:vec)
			{
//				cout<<z.first<<' '<<z.second<<' '<<i<<endl;
				if(z.first>r) ll++;
				r=max(r,z.second);
			}
			ans+=(ll*2+1)*(ls[i+1].y1-ls[i].y1);
			vec.clear();
		}
	}
	printf("%d",ans);
	return 0;
}