算法复习之坐标离散化
标签：target 输出 end unique str http ++ pac com
离散化概念
例子：
1.
描述： 在桌子上放了N个平行于坐标轴的矩形，这N个矩形可能有互相覆盖的部分，求它们组成的图形的面积。
输入格式：输入第一行为一个数N(1
和右上角的坐标，坐标范围为-10^8到10^8之间的整数。
输出格式：
输出只有一行，一个整数，表示图形面积。
样例输入：
3
1 1 4 3
2 -1 3 2
4 0 5 2
样例输出：
10
#include
#include
using namespace std;
const int maxn=210;
int x1[maxn],y1[maxn],x2[maxn],y2[maxn],x[maxn],y[maxn];
void init() {
for(int i=0; i) {
x1[i]=y1[i]=x2[i]=y2[i]=x[i]=y[i]=0;
}
}
int main() {
int n;
while(cin>>n) {
init();
for(int i=1; i) {
cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
x[2*i-1]=x1[i];
x[2*i]=x2[i];
y[2*i-1]=y1[i];
y[2*i]=y2[i];
}
sort(x+1,x+2*n+1);
sort(y+1,y+2*n+1);
int sum=0;
//枚举每一个单位，，判断是否符合条件
for(int i=1; i2*n-1; i++)
for(int j=1; j2*n-1; j++) {
int s=((x[i+1]-x[i])*(y[i+1]-y[i]));
for(int k=1; k) {
if(x[i]>=x1[k]&&y[i]>=y1[k]&&x[i+1]1]y2[k]) {
sum+=s;
break;
}
}
}
coutendl;
}
return 0;
}
2.来自《挑战程序设计竞赛》
区域的个数
w*h的各自上画了n条垂直或水平的宽度为1的直线，求出这些线将格子划分成了多少个区域。
限制条件：1
利用数组存储搜索即可，问题在于数的范围太大，所以要利用坐标离散化，数组中只需存储有直线的行列，及其前后的行列就够了。
//离散化函数，对坐标x1,x2进行离散化，并返回离散化之后的宽度
//其中x1,x2代表一条直线开头与结尾的列 y为行
//重新形成一个数组
#include
#include
#include
#includeint Compress(int *x1,int *x2,int w) {
vectorint> s;//只需存前后及自身坐标
for(int i=0; i) {
for(int d=-1; d1; d++) {
//首先判断前后
int tx1=x1[i]+d;
int tx2=x2[i]+d;
if(1w) s.push_back(tx1);
if(1w) s.push_back(tx2);
//进行排序删除重复的
}
}
sort(s.begin(),s.end());
s.erase(unique(s.begin(),s.end()),s.end());
//重新分配顺序
for(int i=0; i) {
x1[i]=find(s.begin(),s.end(),x1[i])-s.begin();
x2[i]=find(s.begin(),s.end(),x2[i])-s.begin();
}
return s.size();
}
算法复习之坐标离散化
标签：target 输出 end unique str http ++ pac com
原文地址：https://www.cnblogs.com/wtblogwt/p/9750312.html
评论