近來實驗室給派了新活，跟原來做的東西，以及我們熟悉的東西都比較不搭邊的，郁悶。
折騰了兩個星期，昨天終于有了些進展。
今天做了兩道水題~ 都是貪心
思路：
這題看上去挺唬人，提交的人也不多，實際上都是水題來的。
1. 對于同一種字母，求出它出現位置的最左邊、最右邊、最上邊、最下邊。這就構成了一個矩形。
2. 對于在x軸上投影重合的一系列矩形，他們必定處在同一個方格內。給這些方格編號。
3. 對于在y軸上投影重合的一系列矩形，如果其中兩個編號相同，就不符合條件了。
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct rect 
{
int left, right, top, bottom;
int rank_x;
} rec[32];
int T, K, P;
int cmp_x(const void *a, const void *b)
{
return ((struct rect *)a)->left - ((struct rect *)b)->left;
}
int cmp_y(const void *a, const void *b)
{
return ((struct rect *)a)->top - ((struct rect *)b)->top;
}
inline int solve()
{
int i, last, rank, mask;
qsort(rec, K, sizeof(rec[0]), cmp_x);
rank = 0;
for (i = 0; i < K; ) {
last = rec[i].right;
while (i < K && rec[i].left <= last) {
rec[i].rank_x = rank;
last = max(last, rec[i].right);
i++;
}
rank++;
}
qsort(rec, K, sizeof(rec[0]), cmp_y);
for (i = 0; i < K; ) {
mask = 0;
last = rec[i].bottom;
while (i < K && rec[i].top <= last) {
if (mask & (1 << rec[i].rank_x))
return 0;
mask |= 1 << rec[i].rank_x;
last = max(last, rec[i].bottom);
i++;
}
}
return 1;
}
int main()
{
int i, j, x, y;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &K, &P);
for (i = 0; i < K; i++) {
rec[i].left = rec[i].top = 1000000;
rec[i].right = rec[i].bottom = 0;
for (j = 0; j < P; j++) {
scanf("%d%d", &x, &y);
if (x < rec[i].left)
rec[i].left = x;
if (x > rec[i].right)
rec[i].right = x;
if (y < rec[i].top)
rec[i].top = y;
if (y > rec[i].bottom)
rec[i].bottom = y;
}
}
printf("%s\n", solve() ? "YES" : "NO");
}
return 0;
}