題意：
給出一些瓷磚，以及需要鋪的面積w*h（從(0,0)到(w,h)），求：
（1）這些瓷磚是否有重疊
（2）這些瓷磚是否超過了地面的邊界
（3）這些瓷磚能否完整的鋪蓋地面
瓷磚個(gè)數(shù)n<100
解法：
對(duì)于第一問，傳統(tǒng)的做法應(yīng)該是離散化+線段樹。但是此題數(shù)據(jù)量很小，n<100離散化后面積不過160000，可以暴力判重。
對(duì)于第二問，掃描一遍即可
對(duì)于第三問，計(jì)算下總面積即可。
代碼：
1 # include <cstdio>
2 using namespace std;
3 # include <vector>
4 # include <algorithm>
5 # include <cstring>
6 int data[101][4],c1,tmp1[500],c2,tmp2[500],n,w,h;
7 bool used[500][500];
8 int main()
9 {
10 int test;
11 scanf("%d",&test);
12 while(test--)
13 {
14 int total=0;
15 scanf("%d%d%d",&w,&h,&n);
16 c1=c2=0;
17 memset(used,0,sizeof(used));
18 for(int i=0;i<n;i++)
19 {
20 scanf("%d%d%d%d",&data[i][0],&data[i][1],&data[i][2],&data[i][3]);
21 tmp1[c1++]=data[i][0];
22 tmp1[c1++]=data[i][2]-1;
23 tmp2[c2++]=data[i][1];
24 tmp2[c2++]=data[i][3]-1;
25 }
26 sort(tmp1,tmp1+c1);
27 c1=unique(tmp1,tmp1+c1)-tmp1;
28 sort(tmp2,tmp2+c2);
29 c2=unique(tmp2,tmp2+c2)-tmp2;
30 for(int i=0;i<n;i++)
31 {
32 int xl=lower_bound(tmp1,tmp1+c1,data[i][0])-tmp1,xh=lower_bound(tmp1,tmp1+c1,data[i][2]-1)-tmp1;
33 int yl=lower_bound(tmp2,tmp2+c2,data[i][1])-tmp2,yh=lower_bound(tmp2,tmp2+c2,data[i][3]-1)-tmp2;
34 for(int j=xl;j<=xh;j++)
35 for(int k=yl;k<=yh;k++)
36 if(used[j][k])
37 {
38 printf("NONDISJOINT\n");
39 goto end;
40 }
41 else used[j][k]=true;
42 }
43 for(int i=0;i<n;i++)
44 if(data[i][0]<0||data[i][0]>w||data[i][2]<0||data[i][2]>w||data[i][1]<0||data[i][1]>h||data[i][3]<0||data[i][3]>h)
45 {
46 printf("NONCONTAINED\n");
47 goto end;
48 }
49 for(int i=0;i<n;i++)
50 total+=(data[i][2]-data[i][0])*(data[i][3]-data[i][1]);
51 if(total!=w*h) printf("NONCOVERING\n");
52 else printf("OK\n");
53 end:;
54 }
55 }
56