分析: 题目的意思很好理解,就是选择满足在 H1--H2,与A1---A2 之间的最大的 L。 显然该用二维线段树来做,代码很好写,需要注意 H1 > H2 和 A1 > A2 的情况。 另外还需要采用double 型。
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) code 1 #include<iostream> 2 using namespace std; 3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 4 const int maxn=4000; 5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 6 struct node_y 7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 8 int left,right; 9 int mid; 10 double max; 11 }; 12![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 13 struct node_x 14![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 15 int left,right; 16 int mid; 17 node_y Y[maxn]; 18 }; 19![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 20 node_x X[400]; 21![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 22 void Creat_y(node_x &x,int id,int from,int to) 23![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 29 if(from==to) return ; 30![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 35 void Creat_tree(int id,int from,int to) 36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 42 if(from==to)return ; 43![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 44 Creat_tree(2*id,from,X[id].mid); 45 Creat_tree(2*id+1,X[id].mid+1,to); 46 } 47![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 48 int Update_y(node_x &x,int id,int a,float luck) 49![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 61 int Update_x(int id,int h,int a,float luck) 62![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 63 64 Update_y(X[id],1,a,luck); 65![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 75 float Find_y(node_x &x,int id,int a1,int a2) 76![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 77 if(x.Y[id].left==a1 && x.Y[id].right==a2) 78 return x.Y[id].max; 79![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 88 return l1>l2? l1:l2; 89 } 90![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 91 float Find_x(int id,int h1,int h2,int a1,int a2) 92![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 93 float l1,l2; 94![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 95 if(X[id].left==h1&&X[id].right==h2) 96![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 110 int main() 111![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 118 Creat_tree(1,1,101); 119 while(m--) 120![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 121 getchar(); 122 scanf("%c",&c); 123 if(c=='I') 124![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 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 }
|