題意是這樣，平面上有很多點，過一點的十字交叉線將平面分為4個部分，求某條掃描線的使得左下平面和右上平面中的點的最小值最大。
這道題比較有意思，用2個樹結構進行維護，左邊的樹為空，右邊的樹包含所有點，按照點的x、y坐標排序，一個掃面線過去，左邊的樹增加點，右邊的樹刪除點，進行動態統計~。至于樹結構什么都可以，直接套set估計也能過，由于我在做線段樹、樹狀數組專題，就用樹狀數組來實現吧，不過需要離散化，55
貼代碼
1 import java.io.*;
2 import java.util.*;
3 public class Main {
4
5 /**
6 * @param args
7 */
8 static int arr1[]=new int[200005],arr2[]=new int[200005],n,c;
9 static class node implements Comparable<node>
10 {
11 int x,y;
12 public int compareTo(node pos)
13 {
14 if(x!=pos.x)
15 return x-pos.x;
16 else
17 return y-pos.y;
18 }
19 }
20 static void add(int pos,int val,int arr[])
21 {
22 for(;pos<=n;pos+=pos&(-pos))
23 arr[pos]+=val;
24 }
25 static int sum(int pos,int arr[])
26 {
27 int res=0;
28 for(;pos>0;pos-=pos&(-pos))
29 res+=arr[pos];
30 return res;
31 }
32 static TreeMap<Integer,Integer> refer=new TreeMap<Integer,Integer>();
33 static node data[]=new node[200005];
34 static ArrayList<Integer> tres=new ArrayList<Integer>(),res=new ArrayList<Integer>();
35 public static void main(String[] args) throws IOException{
36 StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
37 for(int i=0;i<=200000;i++)
38 data[i]=new node();
39 while(true)
40 {
41 in.nextToken();
42 n=(int)in.nval;
43 if(n==0) break;
44 refer.clear();
45 for(int i=0;i<n;i++)
46 {
47 in.nextToken();
48 data[i].x=(int)in.nval;
49 in.nextToken();
50 data[i].y=(int)in.nval;
51 refer.put(data[i].y, 0);
52 }
53 Set<Integer> tmp=refer.keySet();
54 c=1;
55 Arrays.fill(arr1, 0);
56 Arrays.fill(arr2, 0);
57 Arrays.sort(data, 0, n);
58 for(Integer p:tmp)
59 refer.put(p, c++);
60 c--;
61 for(int i=0;i<n;i++)
62 {
63 data[i].y=refer.get(data[i].y);
64 add(data[i].y,1,arr2);
65 }
66 tres.clear();
67 res.clear();
68 int value=0,minvalue=Integer.MAX_VALUE;
69 int lastx=data[0].x,begin=0;
70 for(int i=0;i<n;i++)
71 {
72 if(data[i].x!=lastx)
73 {
74 for(int j=begin;j<i;j++)
75 {
76 add(data[j].y,-1,arr2);
77 }
78 for(int j=begin;j<i;j++)
79 {
80 minvalue=Math.min(minvalue, sum(data[j].y-1,arr1)+sum(c,arr2)-sum(data[j].y,arr2));
81 tres.add(sum(c,arr1)-sum(data[j].y,arr1)+sum(data[j].y-1,arr2));
82 }
83 for(int j=begin;j<i;j++)
84 {
85 add(data[j].y,1,arr1);
86 }
87 if(minvalue>value)
88 {
89 value=minvalue;
90 res.clear();
91 res.addAll(tres);
92 }
93 else if(minvalue==value)
94 res.addAll(tres);
95 tres.clear();
96 begin=i;
97 lastx=data[i].x;
98 minvalue=Integer.MAX_VALUE;
99 }
100 }
101 if(res.isEmpty()) res.add(0);
102 System.out.print("Stan: "+value+"; Ollie: ");
103 Collections.sort(res);
104 System.out.print(res.get(0));
105 for(int i=1;i<res.size();i++)
106 if(!res.get(i).equals(res.get(i-1)))
107 System.out.print(" "+res.get(i));
108 System.out.println(";");
109
110 }
111
112 }
113
114 }
115