离散化第一点tle了
查看原帖
离散化第一点tle了
1139221
Agil12_楼主2024/5/1 11:33
//还有扫描线做法?
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e4+10;
struct no
{
	int x1,x2,y1,y2;
}q[N];
short c[N][N];
ll ans;
int n;
vector<int>a,b;
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>q[i].x1>>q[i].y1>>q[i].x2>>q[i].y2;
		a.push_back(q[i].x1);
		a.push_back(q[i].x2);
		b.push_back(q[i].y1);
		b.push_back(q[i].y2);
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	a.erase(unique(a.begin(),a.end()),a.end());
	b.erase(unique(b.begin(),b.end()),b.end());
	for(int i=0;i<n;i++)
	{
		int x1,y1,x2,y2;
		x1=lower_bound(a.begin(),a.end(),q[i].x1)-a.begin();
		x2=lower_bound(a.begin(),a.end(),q[i].x2)-a.begin();
		y1=lower_bound(b.begin(),b.end(),q[i].y1)-b.begin();
		y2=lower_bound(b.begin(),b.end(),q[i].y2)-b.begin();
		
		for(int j=x1;j<x2;j++)
		for(int k=y1;k<y2;k++)
		c[j][k]=1;
		
		
	}
	for(int i=0;i<a.size()-1;i++)
	for(int j=0;j<b.size()-1;j++)
	if(c[i][j])ans+=(ll)(a[i+1]-a[i])*(b[j+1]-b[j]);
	cout<<ans;
	
	return 0;
}
2024/5/1 11:33
加载中...