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
這道題用了離散化的方法
其實(shí)最樸素的方法就是在一個(gè)20000*20000的矩陣上面把所有的點(diǎn)描出來，然后把這些點(diǎn)的周長(zhǎng)算出來，不過算周長(zhǎng)這一步也是很麻煩的。
因?yàn)楫吘惯€有可能出現(xiàn)“空心”的情況
用離散化的方法就是想辦法只數(shù)每條線段，而不去管其他空白的地方是怎么樣的。
由于我們是需要算周長(zhǎng)的，所以只需要看矩形的四條邊就可以了。
然后，我們就是先看所有的橫邊，再看豎邊。
先把橫邊全部選出來，放在一個(gè)數(shù)組里面，然后排序，從下到上。
一個(gè)矩形的兩條邊要分成始邊和終邊，排序的時(shí)候，如果縱坐標(biāo)相同，那么應(yīng)該把始邊放在終邊。
如果遇到始邊，那么就把這條邊上面的所有點(diǎn)level[j]加一。
如果遇到終邊，就把那條邊上所有的點(diǎn)的level[j]減一
于是，當(dāng)一條邊上的點(diǎn)的leve是1的時(shí)候，那么就說明這條邊肯定是始邊邊緣，所以要ans++
另一種情況，當(dāng)一條邊上的點(diǎn)的level是0的時(shí)候，那么說明這個(gè)點(diǎn)是終邊邊緣，所以ans++
這樣掃完橫邊再掃豎邊。
最后的ans就是周長(zhǎng)了。
不過這個(gè)算法的時(shí)間效率并不是非常的好，因?yàn)閿?shù)據(jù)比較弱（可能是這樣）
如果真的是有5000個(gè)矩形，沒個(gè)矩形都是20000×20000的，那么可能會(huì)超時(shí)