【2019杭电多校训练赛】HDU6681 / 1002-Rikka with Cake 题解（扫描线）

题目来自于：HDU6681 Rikka with Cake

题意

题目的大意是给定你一个（n, m）的长方形，然后这个长方形里面有许多条射线，然后问这么多条射线把平面分割成了多少个区域，这些射线由起点加一个方向表示。
和这题题目像可是是不一样的题目 HDU 6665 Calabash and Landlord（题目大意是将两个矩形组合看能分成多少个区域）

思路

我们可以找规律并且猜想得出，其实分割的数量等于交点个数+1。然后我们可以用扫描线的方法（不会）来写这道题目，直接贴上标程：

代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
const int N=110000;
struct atom{
	int x,y;
};
vector<atom> A[4],x,y;
char ch[10];
int n,m,K;
void readpoint(){
	int x,y; scanf("%d%d%s",&x,&y,ch+1);
	int z=0;
	if (ch[1]=='L') z=0; else if (ch[1]=='R') z=1; else if (ch[1]=='D') z=2; else z=3;
	A[z].push_back((atom){x,y});
}
struct atom2{
	int x,y,pd;
};
vector<atom2>Q;
int B[N],len,C[N];
void add(int k1){
	for (;k1<=len;k1+=k1&(-k1)) C[k1]++;
}
int find(int k1){
	int ans=0;
	for (;k1;k1-=k1&(-k1)) ans+=C[k1];
	return ans;
}
int comparex(atom2 k1,atom2 k2){
	return k1.x<k2.x;
}
int comparey(atom2 k1,atom2 k2){
	return k1.y<k2.y;
}
long long getcross(){
	Q.clear();
	for (int i=0;i<x.size();i++) Q.push_back((atom2){x[i].x,x[i].y,0});
	for (int i=0;i<y.size();i++) Q.push_back((atom2){y[i].x,y[i].y,1});
	sort(Q.begin(),Q.end(),comparey); len=0;
	for (int i=0;i<Q.size();i++) Q[i].y=++len;
	sort(Q.begin(),Q.end(),comparex);
	//cout<<"getcross"<<endl;
	//for (int i=0;i<Q.size();i++) cout<<Q[i].x<<" "<<Q[i].y<<" "<<Q[i].pd<<endl;
	for (int i=1;i<=len;i++) C[i]=0;
	long long ans=0;
	int tot=0;
	for (int i=0;i<Q.size();i++)
		if (Q[i].pd==0) ans+=tot-find(Q[i].y); else {add(Q[i].y); ++tot;}
	return ans;
}
void solve(){
	scanf("%d%d%d",&n,&m,&K);
	for (int i=0;i<4;i++) A[i].clear();
	for (int i=1;i<=K;i++) readpoint();
	long long cross=0;
	x=A[0],y=A[2]; cross+=getcross();
	x=A[0],y=A[3];
	for (int i=0;i<x.size();i++) x[i].y=m-x[i].y;
	for (int i=0;i<y.size();i++) y[i].y=m-y[i].y;
	cross+=getcross();
	x=A[1]; y=A[2];
	for (int i=0;i<x.size();i++) x[i].x=n-x[i].x;
	for (int i=0;i<y.size();i++) y[i].x=n-y[i].x;
	cross+=getcross();
	x=A[1]; y=A[3];
	for (int i=0;i<x.size();i++) x[i].x=n-x[i].x,x[i].y=m-x[i].y;
	for (int i=0;i<y.size();i++) y[i].x=n-y[i].x,y[i].y=m-y[i].y;
	cross+=getcross();
	long long totV=cross+K*2+4;
	long long totE=4+K*2+cross*2;
	printf("%lldn",totE-totV+1);
}
int main(){
	int t; scanf("%d",&t);
	for (;t;t--) solve();
	return 0;
}

最后

以上就是甜蜜汽车最近收集整理的关于【2019杭电多校训练赛】HDU6681 / 1002-Rikka with Cake 题解（扫描线）的全部内容，更多相关【2019杭电多校训练赛】HDU6681内容请搜索靠谱客的其他文章。