1 import java.io.*;
 2 import java.util.*;
 3 /*
 4 ID: yanglei4
 5 LANG: JAVA
 6 TASK:picture
 7 */
 8 public class picture {
 9     public int[] level;
10     public int N;
11     public int ans = 0;
12     
13     public class Line implements Comparable<Line> {
14         int s,t,p;
15         boolean start;
16         public Line(int a, int b, int c, boolean d) {
17             s = a;
18             t = b;
19             p = c;
20             start = d;
21         }
22         public int compareTo(Line o) {
23             if (this.p == o.p) {
24                 if (this.start)
25                     return -1;
26                 else
27                     return 1;
28             }
29             return this.p < o.p ? -1 : 1;
30         }
31     }
32     public void Scan(Line[] L) {
33         for (int i = 0;i <= 20000;i++)
34             level[i] = 0;
35         for (int i = 0; i < 2 * N;i++) {
36             if (L[i].start) {
37                 for (int j = L[i].s;j < L[i].t;j++) {
38                     level[j]++;
39                     if (level[j]==1)
40                         ans++;
41                 }
42             }
43             else {
44                 for (int j = L[i].s;j < L[i].t;j++) {
45                     level[j]--;
46                     if (level[j]==0)
47                         ans++;
48                 }
49             }
50         }
51     }
52     public void done() throws IOException {
53         BufferedReader f = new BufferedReader(new FileReader("picture.in"));
54         PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("picture.out")));
55         N = Integer.parseInt(f.readLine());
56         Line[] Lx = new Line[2 * N];
57         Line[] Ly = new Line[2 * N];
58         
59         for (int i = 0; i < N; i++) {
60             StringTokenizer st = new StringTokenizer(f.readLine());
61             int x1 = Integer.parseInt(st.nextToken());//left x
62             int y1 = Integer.parseInt(st.nextToken());//left y
63             int x2 = Integer.parseInt(st.nextToken());//right x
64             int y2 = Integer.parseInt(st.nextToken());//right y
65             x1 += 10000;
66             y1 += 10000;
67             x2 += 10000;
68             y2 += 10000;
69             Lx[2 * i] = new Line(x1,x2,y1,true);
70             Lx[2 * i + 1= new Line(x1,x2,y2,false);
71             Ly[2 * i] = new Line(y1,y2,x1,true);
72             Ly[2 * i + 1= new Line(y1,y2,x2,false);
73         }
74         Arrays.sort(Lx);
75         Arrays.sort(Ly);
76         level = new int[20001];
77         Scan(Lx);
78         Scan(Ly);
79         out.println(ans);
80         
81         out.close();    
82     }
83     public static void main(String[] args) throws IOException {
84         picture t = new picture();
85         t.done();
86         System.exit(0);
87     }
88 }
89 

这道题用了离散化的方法

其实最朴素的方法就是在一个20000*20000的矩阵上面把所有的点描出来,然后把这些点的周长算出来,不过算周长这一步也是很麻烦的。

因为毕竟还有可能出现“空心”的情况

用离散化的方法就是想办法只数每条线段,而不去管其他空白的地方是怎么样的。

由于我们是需要算周长的,所以只需要看矩形的四条边就可以了。

然后,我们就是先看所有的横边,再看竖边。

先把横边全部选出来,放在一个数组里面,然后排序,从下到上。

一个矩形的两条边要分成始边和终边,排序的时候,如果纵坐标相同,那么应该把始边放在终边。

如果遇到始边,那么就把这条边上面的所有点level[j]加一。

如果遇到终边,就把那条边上所有的点的level[j]减一

于是,当一条边上的点的leve是1的时候,那么就说明这条边肯定是始边边缘,所以要ans++

另一种情况,当一条边上的点的level是0的时候,那么说明这个点是终边边缘,所以ans++

这样扫完横边再扫竖边。

最后的ans就是周长了。

不过这个算法的时间效率并不是非常的好,因为数据比较弱(可能是这样)

如果真的是有5000个矩形,没个矩形都是20000×20000的,那么可能会超时