MS好久不寫blog了，現(xiàn)在好忙，又是GRE，又是考研，又是ACM。。蛋疼
言歸正傳
題意:
給出一些長方形，不重疊，但可以擦邊或擦角。問有多少個(gè)長方形是完全不和別的長方形沾邊的
給力條件：不重疊
方法：經(jīng)典的排序+區(qū)間合并
代碼：
1 # include <cstdio>
2 # include <cstring>
3 # include <cstdlib>
4 # define max(a,b) ((a)>(b)?(a):(b))
5 using namespace std;
6 struct line
7 {
8 int s,e,p,id;
9 }tmp[60000];
10 int cmp(const void *a,const void *b)
11 {
12 line *aa=(line *)a,*bb=(line *)b;
13 if(aa->p!=bb->p) return aa->p-bb->p;
14 else return aa->s-bb->s;
15 }
16 int data[30000][4],n;
17 bool used[30000];
18 void solve()
19 {
20 int end=tmp[0].e,last=0;
21 for(int i=1;i<2*n;i++)
22 if(tmp[i].p==tmp[i-1].p&&tmp[i].s<=end)
23 end=max(end,tmp[i].e);
24 else
25 {
26 if(last!=i-1)
27 for(int j=last;j<i;j++)
28 used[tmp[j].id]=false;
29 end=tmp[i].e;
30 last=i;
31 }
32 if(last!=2*n-1)
33 for(int j=last;j<2*n;j++)
34 used[tmp[j].id]=false;
35 }
36 int main()
37 {
38 scanf("%d",&n);
39 memset(used,true,sizeof(used));
40 for(int i=0;i<n;i++)
41 scanf("%d%d%d%d",&data[i][0],&data[i][1],&data[i][2],&data[i][3]);
42 for(int i=0;i<n;i++)
43 {
44 tmp[2*i].s=data[i][0];
45 tmp[2*i].e=data[i][2];
46 tmp[2*i].p=data[i][1];
47 tmp[2*i].id=i;
48 tmp[2*i+1]=tmp[2*i];
49 tmp[2*i+1].p=data[i][3];
50 }
51 qsort(tmp,2*n,sizeof(line),cmp);
52 /* printf("\n");
53 for(int i=0;i<2*n;i++)
54 printf("%d %d %d %d\n",tmp[i].id,tmp[i].p,tmp[i].s,tmp[i].e);
55 printf("\n");*/
56 solve();
57 for(int i=0;i<n;i++)
58 {
59 tmp[2*i].s=data[i][1];
60 tmp[2*i].e=data[i][3];
61 tmp[2*i].p=data[i][0];
62 tmp[2*i].id=i;
63 tmp[2*i+1]=tmp[2*i];
64 tmp[2*i+1].p=data[i][2];
65 }
66 qsort(tmp,2*n,sizeof(line),cmp);
67 /* for(int i=0;i<2*n;i++)
68 printf("%d %d %d %d\n",tmp[i].id,tmp[i].p,tmp[i].s,tmp[i].e);
69 printf("\n");*/
70 solve();
71 int c=0;
72 for(int i=0;i<n;i++)
73 c+=used[i];
74 printf("%d\n",c);
75 //system("pause");
76 return 0;
77 }
78