原文地址：
需求：
n个与直角坐标系平行的矩形，可能重叠，要求出总面积（重叠部分只算一次）
样例
思路：
这题按照最平常的想法就是把矩形内的标记，然后整个图搜索，就可以得出共覆盖了多少范围。但是范围是-10^8~10^8，这么搜显然不可能。所以要怎么样呢？
就是把有用的点保存，无关的点压缩。什么是有用的点保存，什么是无关的点压缩？给出的坐标就是有用的点，-10^8~10^8内的范围内除了给出的坐标范围其他全是没用的点，都要压缩。
有用的值其实只有这么几个。这些值将作为新的坐标值重新划分整个平面，省去中间的若干坐标值没有影响。我们可以将坐标范围“离散化”到1到200
之间的数，于是一个200*200的二维数组就足够了。
样例：
现在用个小例子来模拟一下：
注意左边的10* 7的数组是如何等价地转化为右边两个4*4的数组的
image
再就是代码实现了：
image
如上数据示例
x[ ]={ 1, 3, 7, 10 };
y[ ]={ 1, 2, 5, 7 };
按代码枚举的顺序是如上图，先看(1,1)点， if(x[i]>=x1[k]&&y[j]>=y1[k]&&x[i+1]<=x2[k]&&y[j+1]<=y2[k])判断是否是矩形内的然后按顺序枚举，发现（1,1）点不是，再看（1,2）点，s=s(x+1,y+1)-s(x,y)即框2，符合在矩形内，ans+=s,枚举完了，就得出结果了
C语言代码：
include<cstdio>
include<cstdlib>
include<algorithm>
include<iostream>
define MAXn 100
using namespace std;
int n;
long long x1[MAXn+1],y1[MAXn+1];
long long x2[MAXn+1],y2[MAXn+1];
long long x[2MAXn+1],y[2MAXn+1];
long long S,ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%I64d%I64d%I64d%I64d",&x1[i],&y1[i],&x2[i],&y2[i]);
x[2i-1]=x1[i];
x[2i]=x2[i];
y[2i-1]=y1[i];
y[2i]=y2[i];
}
sort(x+1,x+2n+1);
sort(y+1,y+2n+1);
for(int i=1;i<=2n-1;i++) //枚举每一个单位横坐标，这两句看图
for(int j=1;j<=2n-1;j++) //枚举每一个单位纵坐标
{
S=(x[i+1]-x[i])*(y[j+1]-y[j]);
for(int k=1;k<=n;k++) //枚举每一个矩形块
if(x[i]>=x1[k]&&y[j]>=y1[k]&&x[i+1]<=x2[k]&&y[j+1]<=y2[k])//这句是离散化
{ ans+=S; break; }//注意这个break,用的妙
}
printf("%I64d",ans); return 0;
}
java代码(按C语言版本直接移植过来)：
import java.util.Scanner;
public class MainClass {
private static void sort(int[] nums) {
sort(nums, 0, nums.length - 1);
}
private static void sort(int[] nums, int startIndex, int stopIndex) {
if (null != nums) {
for (int i = startIndex; i < stopIndex; i++) {
for (int j = startIndex; j < stopIndex - i; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入矩形个数:");
String string = scanner.nextLine();
int count = 0;
try {
count = Integer.parseInt(string);
} catch (Exception e) {
System.out.println("输入错误\n");
return;
}
System.out.println("分别输入" + count + "个矩形坐标,格式[lx ly rx ry]:");
final int MAXn = 100;
if (count > MAXn) {
count = MAXn;
}
int x1[] = new int[count + 1];
int y1[] = new int[count + 1];
int x2[] = new int[count + 1];
int y2[] = new int[count + 1];
int x[] = new int[2 * count + 1];
int y[] = new int[2 * count + 1];
for (int i = 1; i <= count; i++) {
x1[i] = scanner.nextInt();
y1[i] = scanner.nextInt();
x2[i] = scanner.nextInt();
y2[i] = scanner.nextInt();
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, 2 * count + 1);
sort(y, 1, 2 * count + 1);
long S = 0, ans = 0;
for (int i = 1; i <= 2 * count - 1; i++) // 枚举每一个单位横坐标，这两句看图
for (int j = 1; j <= 2 * count - 1; j++) // 枚举每一个单位纵坐标
{
S = (x[i + 1] - x[i]) * (y[j + 1] - y[j]);
for (int k = 1; k <= count; k++) // 枚举每一个矩形块
if (x[i] >= x1[k] && y[j] >= y1[k] && x[i + 1] <= x2[k] && y[j + 1] <= y2[k])// 这句是离散化
{
ans += S;
break;
} // 注意这个break,用的妙
}
System.out.println("ans:" + ans);
}
}
网友评论