分析：
题目的意思很好理解，就是选择满足在 H1--H2,与A1---A2 之间的最大的 L。
显然该用二维线段树来做，代码很好写，需要注意 H1 > H2 和 A1 > A2 的情况。
另外还需要采用double 型。
  code
1 #include<iostream>
2using namespace std;
3
4const int maxn=4000;
5
6struct node_y
7 {
8 int left,right;
9 int mid;
10 double max;
11 };
12
13struct node_x
14{
15 int left,right;
16 int mid;
17 node_y Y[maxn];
18};
19
20node_x X[400];
21
22void Creat_y(node_x &x,int id,int from,int to)
23{
24 x.Y[id].left=from;
25 x.Y[id].right=to;
26 x.Y[id].mid=(from+to)>>1;
27 x.Y[id].max=-1;
28
29 if(from==to) return ;
30
31 Creat_y(x,2*id,from,x.Y[id].mid);
32 Creat_y(x,2*id+1,x.Y[id].mid+1,to);
33}
34
35void Creat_tree(int id,int from,int to)
36{
37 X[id].left=from;
38 X[id].right=to;
39 X[id].mid=(from+to)>>1;
40 Creat_y(X[id],1,1,1001);
41
42 if(from==to)return ;
43
44 Creat_tree(2*id,from,X[id].mid);
45 Creat_tree(2*id+1,X[id].mid+1,to);
46}
47
48int Update_y(node_x &x,int id,int a,float luck)
49{
50 if(luck>x.Y[id].max)x.Y[id].max=luck;
51
52 if(x.Y[id].left==x.Y[id].right)
53 return 1;
54 if(a<=x.Y[id].mid)
55 Update_y(x,2*id,a,luck);
56 else
57 Update_y(x,2*id+1,a,luck);
58 return 1;
59}
60
61int Update_x(int id,int h,int a,float luck)
62{
63
64 Update_y(X[id],1,a,luck);
65
66 if(X[id].left==X[id].right)
67 return 1;
68 if(h<=X[id].mid)
69 Update_x(2*id,h,a,luck);
70 else
71 Update_x(2*id+1,h,a,luck);
72 return 1;
73}
74
75float Find_y(node_x &x,int id,int a1,int a2)
76{
77 if(x.Y[id].left==a1 && x.Y[id].right==a2)
78 return x.Y[id].max;
79
80 if(a2<=x.Y[id].mid)
81 return Find_y(x,2*id,a1,a2);
82 if(a1>x.Y[id].mid)
83 return Find_y(x,2*id+1,a1,a2);
84
85 float l1=Find_y(x,2*id,a1,x.Y[id].mid);
86 float l2=Find_y(x,2*id+1,x.Y[id].mid+1,a2);
87
88 return l1>l2? l1:l2;
89}
90
91float Find_x(int id,int h1,int h2,int a1,int a2)
92{
93 float l1,l2;
94
95 if(X[id].left==h1&&X[id].right==h2)
96  {
97 return Find_y(X[id],1,a1,a2);
98 }
99 if(h2<=X[id].mid)
100 return Find_x(2*id,h1,h2,a1,a2);
101 if(h1>X[id].mid)
102 return Find_x(2*id+1,h1,h2,a1,a2);
103
104 l1=Find_x(2*id,h1,X[id].mid,a1,a2);
105 l2=Find_x(2*id+1,X[id].mid+1,h2,a1,a2);
106
107 return l1>l2? l1:l2;
108}
109
110int main()
111{
112 int H,A,H1,H2,A1,A2,m;
113 double L,L1,L2,luck;
114 char c;
115
116 while(EOF!=scanf("%d",&m)&&m)
117 {
118 Creat_tree(1,1,101);
119 while(m--)
120 {
121 getchar();
122 scanf("%c",&c);
123 if(c=='I')
124 {
125 scanf("%d%lf%lf",&H,&L,&luck);
126 A=int( L*10)+1;
127 Update_x(1,H-99,A,luck);
128 }
129 else
130 {
131 scanf("%d%d%lf%lf",&H1,&H2,&L1,&L2);
132 A1=int(L1*10)+1;
133 A2=int(L2*10)+1;
134
135 if(A1>A2)swap(A1,A2);
136 if(H1>H2)swap(H1,H2);
137
138 luck=Find_x(1,H1-99,H2-99,A1,A2);
139
140 if(luck<0)printf("-1\n");
141 else printf("%.1lf\n",luck);
142 }
143 }
144 }
145 return 0;
146}
|