|
|
思路： 一開始想到用線段樹來做，但是發現坐標范圍異常的大，放一個都勉勉強強，更不用說幾個了！ 想了一下，發現有一個至關重要的條件“不存在覆蓋的情況”。 那就沒必要用線段樹了，因為壓根就沒必要解決覆蓋問題。 可以用一種取巧的方法解決這題。  對于每個矩形，首先把它 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;
}
|