Convex hull / Andrew algorithm.

Dot Product && Cross Product.

In 2D-coordinate, we have two point A(x1,y1) and B(x2,y2);
A·B = A*B*Cos(θ);
A×B = x1*y2 - x2*y1;
A×B means the parallelogram's area by line(O->A), line(O->B). Using right hand to show its orientation ( The area's plus-minus ).

Andrew algorithm.

• S1. sort all node by X, if X is same, sort by Y in ascending order.
• S2. Push Point(0), Point(1) in the heap to finish initialization.
• S3. Push the point in order(left->right), and keep the point in stack satisfy that : always maintain convex.
• S4. Same as s3, from right to left.

const int MAXN=1005; //Maximum node number;
struct Node {
    int x,y;
    bool operator<(const Node& rhs) const{
        if (x == rhs.x)
            return y<rhs.y;
        return x<rhs.x;
    };
}node[MAXN];
/* Calculate the cross product of vector{pre->now} and vector{now->nxt}; */
bool isTurnLeft(Node pre, Node now, Node nxt) {
    int x1=now.x-pre.x, y1=now.y-pre.y; //The direction of vector{pre->now}.
    int x2=nxt.x-now.x, y2=nxt.y-now.y; //The direction of vector{now->nxt}.
    return x1*y2-x2*y1>0;
}
int main() {
    cin>>n; // The number of nodes.
    for (int i=0; i<n; i++)
        cin>>node[i].x>>node[i].y;
    sort(node, node+n);
    //The upper-right node and the lower-left node must belong in the convex.
    int stack[MAXN],sTop=0, convex1;
    for (int i=0; i<n; i++) {// The lower half of the convex.
        while (sTop>1 && !isTurnLeft(node[stack[sTop-2]], node[stack[sTop-1]], node[i]) )
            sTop--;
        stack[sTop++] = i;
    }
    // The upper-right node must be at the top of the stack,
    // so we skip the node[n-1] and keep the upper-right node to the 'last node' below.
    convex1 = sTop;
    for (int i=n-2; i>=0; i--) { // The upper half of the convex.
        while (sTop>convex1 && !isTurnLeft(node[stack[sTop-2]], node[stack[sTop-1]], node[i]) )
            sTop--;
        stack[sTop++] = i;
    }
    sTop--; // The last element must same as stack[0] (the lower-left node).
    for (int i=0; i<sTop; i++)
        cout<<stack[i]<<" ";
    cout<<"<< Stack size="<<sTop<<endl;
    return 0;
}

Problem A

There are some Nodes, A(x,y). {x>0, y>0, x is unique(x1!=x2 for each two nodes)}
We select two node {(x1,y1) (x2,y2)} and connect it, and we get a slope k=(y2-y1)/(x2-x1);
Find out the maximum slope k!
给一些点 找两个连起来 求最大斜率

Solution 1 Binary search O(nlogn)

e.g. N=5;
(1,5) (2,3) (3,6) (4,5) (5,20)
We select (x1,y1) (x5,y5) {x1<x2}.
k = (y5-y1)/(x5-x1)
(x5-x1)*k = (y5-y4) + (y4-y3) + (y3-y2) + (y2-y1);

=>using delta45 = y5-y4;
delta45-k + delta34-k + delta23-k + delta12-k = 0 = checkfunction();

F[4]=(delta45-k)
F[3]=(delta34-k)
F[2]=(delta23-k)
...
checkfunction()在F[]上找区间最大和，O（n)
二分答案k
k大了 ===>> checkfunction()<0;
k小了 ===>> checkfunction()>0;

Solution 2 Get the lower half of convex. O(n)

We use std::list and scanning from left to right.
list.front() -> compare with (nextX, nextY) to try the best answer.
list.back() -> to make convex.

list<int> Q;// Node(x,y) =>  x in Q.
// sum[i] = {y1+y2+...+yi }
double ans=-9999999;
//K is the minimum interval of each pair X.
for (int i=k; i<sum.size(); i++) {
    int readyX=i-k, readyY=sum[readyX];
    
    //convex Hull
    while ( Q.size()>1 && slope(*next(Q.rbegin()),Q.back())>slope(*next(Q.rbegin()),readyX) )
        Q.pop_back();
    Q.push_back(readyX);

    //try best answer.
    while ( Q.size()>1 && slope(Q.front(),i)<slope(*next(Q.begin()),i) )
        Q.pop_front();
    ans = max(ans, slope(Q.front(),i));
}

See detail : https://blog.vrqq.org/archives/371/