题目大意：

　　平面直角坐标系内有n个点，每个点有一个点权。

　　你从原点p出发，走若干个点然后回到原点。

　　两个点之间只能笔直走，你的收获为你的路径围起来的区域内的所有店权和除以路径长度。

　　问最大收益。

思路：

　　不难发现：每走一步，相当于在路径形成的多边形中增加一个三角形。

　　我们可以预处理出所有这样以p为顶点的三角形内的点权和。

　　首先对于所有的点极角排序。

　　按极角序枚举每一个点i，作为三角形的第二个顶点。

　　对于极角序在i后面的结点，按照i再排一遍极角序，枚举第三个顶点j。

　　用树状数组二位数点即可。

　　题目是一个经典的分数规划，二份答案再DP判断可行性即可。

　　然而一直95分，用BOJ的数据测也一样，然而并不能找出什么问题。

　　浪费了一个下午，最后被罗大发现是精度问题？

　　反正把最后输出l改成(l+r)/2就A了。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 typedef long long int64; 7 inline int getint() { 8     register char ch; 9     while(!isdigit(ch=getchar()));10     register int x=ch^'0';11     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');12     return x;13 }14 const int B=1001;15 struct Point {16     int x,y;17     bool operator < (const Point &another) const {18         if(y==another.y) return x>another.x;19         return y
          
            a,p;23 std::stack
           
             q;24 int l[B],r[B];25 inline int calc(const int &x,const int &y) {26 if(!x) return 0;27 return (int64)(y*2-std::min(x,y))*(std::min(x,y)-1)/2;28 }29 int main() {30 int n=getint(),m=getint(),b=getint();31 for(register int i=1;i<=b;i++) {32 const int x=getint(),y=getint();33 a.push_back((Point){x,y});34 }35 std::sort(a.begin(),a.end());36 int64 ans=0;37 for(register int i=1;i<=n;i++) {38 p.clear();39 p.push_back((Point){i,0});40 for(register unsigned j=0;j
            
             1&&p[q.top()].x<=p[i].x) q.pop();50 l[i]=q.top();51 q.push(i);52 }53 while(!q.empty()) q.pop();54 q.push(p.size()-1);55 for(register unsigned i=p.size()-2;i>0;i--) {56 while(q.size()>1&&p[q.top()].x