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的，那么可能会超时