簡要描述下題意，一個柵欄圍了一塊地，柵欄只能東西方向或者南北方向放置，柵欄接頭處有一個節(jié)點，節(jié)點僅僅存在于東西方向柵欄與南北方向柵欄之間，給出節(jié)點的坐標，求柵欄的周長。
這道題由于柵欄的特殊性，可以排序+線掃解決。
對東西方向和南北方向的柵欄分別考慮：
對于東西方向的柵欄，先對節(jié)點坐標按照y坐標排序，如果y坐標相等按照x坐標排序。
線性掃描數(shù)組，假設y=y1的節(jié)點從k1到k2，那么此段柵欄的長度為k1~k1+1,k1+2~k1+3...，原因很顯然，柵欄的節(jié)點是按照x順序兩兩配對的。
對于南北方向的柵欄類似處理。
貼代碼：
1 import java.io.*;
2 import java.util.*;
3 public class Main {
4
5 /**
6 * @param args
7 */
8 static class point
9 {
10 int x,y;
11 }
12 static class cmpx implements Comparator<point>
13 {
14 public int compare(point a,point b)
15 {
16 if(a.x!=b.x) return a.x-b.x;
17 else return a.y-b.y;
18 }
19 }
20 static class cmpy implements Comparator<point>
21 {
22 public int compare(point a,point b)
23 {
24 if(a.y!=b.y) return a.y-b.y;
25 else return a.x-b.x;
26 }
27 }
28 static point data[]=new point[100005];
29 public static void main(String[] args) throws IOException{
30 StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
31 for(int i=0;i<data.length;i++)
32 data[i]=new point();
33 while(true)
34 {
35 in.nextToken();
36 int num=(int)in.nval;
37 if(num==0) break;
38 for(int i=0;i<num;i++)
39 {
40 in.nextToken();
41 data[i].x=(int)in.nval;
42 in.nextToken();
43 data[i].y=(int)in.nval;
44 }
45 int len=0;
46 Arrays.sort(data,0,num,new cmpx());
47 int last=0;
48 for(int i=1;i<num;i++)
49 if(data[i].x==data[i-1].x) continue;
50 else
51 {
52 for(int j=last;j<i;j+=2)
53 len+=data[j+1].y-data[j].y;
54 last=i;
55 }
56 for(int j=last;j<num;j+=2)
57 len+=data[j+1].y-data[j].y;
58 Arrays.sort(data,0,num,new cmpy());
59 last=0;
60 for(int i=1;i<num;i++)
61 if(data[i].y==data[i-1].y) continue;
62 else
63 {
64 for(int j=last;j<i;j+=2)
65 len+=data[j+1].x-data[j].x;
66 last=i;
67 }
68 for(int j=last;j<num;j+=2)
69 len+=data[j+1].x-data[j].x;
70 System.out.println("The length of the fence will be "+len+" units.");
71 }
72
73 }
74
75 }
76