|
|
思路： 一开始想到用线段树来做，但是发现坐标范围异常的大，放一个都勉勉强强，更不用说几个了！ 想了一下，发现有一个至关重要的条件“不存在覆盖的情况”。 那就没必要用线段树了，因为压根就没必要解决覆盖问题。 可以用一种取巧的方法解决这题。  对于每个矩形，首先把它 y 方向的两条边抽取出来。 对于所有矩形的 y 方向的边，先按照 x 排序，然后按照顶端的 y 坐标排序。  然后对于位于同一 x 坐标的边，找出所有首尾相接或者有交集的边。 那么这些边对应的矩形必定要排除。 对于 x 方向的边，作同样的处理。 排除完之后，剩下的矩形就是可以答案了。 代码 500 多ms。。
 #include <stdio.h>
#include <stdlib.h>
#define MAX_N 25032
  struct node  {
 int barn, start, end, idx;
 };
struct node vert[MAX_N * 2], hori[MAX_N * 2];
char cannot[MAX_N];
int N, ans;
__inline void add_node(struct node *t, int barn, int start, int end, int idx)
{
t->barn = barn;
t->start = start;
t->end = end;
t->idx = idx;
}
int cmp_node(const void *a, const void *b)
{
struct node *p, *q;
p = (struct node *)a;
q = (struct node *)b;
if (p->idx != q->idx)
return p->idx - q->idx;
return p->start - q->start;
}
__inline void disable_barn(int barn)
{
  if (!cannot[barn]) {
cannot[barn] = 1;
ans--;
 }
}
__inline void calc(struct node *arr, int len)
{
int i, idx, end, cnt, first;
i = 0;
while (i < len) {
idx = arr[i].idx;
end = arr[i].end;
first = i;
cnt = 0;
i++;
while (i < len && arr[i].idx == idx && arr[i].start <= end) {
if (arr[i].end > end)
end = arr[i].end;
disable_barn(arr[i].barn);
cnt++;
i++;
}
if (cnt)
disable_barn(arr[first].barn);
}
}
int main()
{
int i, top, left, bottom, right;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &N);
ans = N;
for (i = 0; i < N; i++) {
scanf("%d%d%d%d", &left, &bottom, &right, &top);
add_node(&vert[i * 2], i, bottom, top, left);
add_node(&vert[i * 2 + 1], i, bottom, top, right);
add_node(&hori[i * 2], i, left, right, top);
add_node(&hori[i * 2 + 1], i, left, right, bottom);
}
qsort(vert, N * 2, sizeof(vert[0]), cmp_node);
qsort(hori, N * 2, sizeof(hori[0]), cmp_node);
calc(vert, N * 2);
calc(hori, N * 2);
printf("%d\n", ans);
return 0;
}
|