熬夜的惩罚

熬夜的惩罚
Problem:A
Time Limit:1000ms
Memory Limit:65535K
Description
卡迪亚得到你给他的答案，就蹦跶蹦跶地去下载游戏了，不过由于游戏太多，一直到晚上12点才下载好。看着这么多好玩的游戏，哪还有心情去睡觉啊，于是悄悄关上房门玩起了游戏。

玩着玩着，就到了凌晨5点，这下完蛋了，早上8点还有课呢！！！ 于是赶紧倒下去睡觉了（玩了这么久游戏哪可能说睡着就睡着啊），果然，第二天早上上网课卡迪亚睡着了，更巧的是，还被他妈妈逮了个正着，妈妈斥责道：还睡觉？你是啥都会了吗？来，给你写一道题。

题目说：一个平面中有n个点，保证点不重合，任意三点不共线，并且这n个点构成的一定是凸边形，这些点按顺时针顺序从1到n编号。现在告诉你1到n每个点的坐标(xi) (yi)。如果有两个点p1,p2，其中p1=(x1,y1)，p2=(x2,y2) ，定义这两点的特殊距离d(p1,p2)=|x1−x2|+|y1−y2|，现在再告诉你需要在这n个点中任意选择k（k≥3）个点，请你找出k个点构成的凸边形在特殊距离公式下的最大周长，其中周长C=d(p1,p2)+d(p2,p3)+…+d(pk,p1)。

为了惩罚你，妈妈让你把所有可能的k的结果都求出来，即求出所有k在[3~n]取值时的答案C。
注意：k个点构成的一定要是凸边形，且边不能够相交，边也必须是直线。下图中左边的图是正确的图，中间的图边相交了，右边的图边不是直线

以下这样的图形就是凸边形

以下这样的图形就不是凸边形

Input
第一行一个整数表示点的数量n (3≤n≤3⋅1e5)
之后n行，每行两个整数，分别表示第i个点的坐标xi，yi (−1e8≤xi,yi≤1e8)
ps：点集是凸的，所有点都是不同的，点是按顺时针顺序排列的，不会有三个共线点。
Output
共一行，分别输出k的取值从3到n时的的每一个结果，每个数之间有一个空格，最后一个数后没有空格。
Sample Input
4
2 4
4 3
3 0
1 3
Sample Output
12 14
Hint
k=3时最大的周长是选2 3 4点。C=4+5+3=12
k=4时最大的周长是选1 2 3 4点 C=3+4+5+2=14

#include <bits/stdc++.h>
using namespace std;
int x[300005];
int y[300005];
int main()
{
    int n;
    cin >> n;
    int max_x=-0x3f3f3f3f;
    int max_y=-0x3f3f3f3f;
    int min_x=0x3f3f3f3f;
    int min_y=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        cin >> x[i] >> y[i];
        max_x=max(max_x,x[i]);
        max_y=max(max_y,y[i]);
        min_x=min(min_x,x[i]);
        min_y=min(min_y,y[i]);
    }
    int c=0;
    for(int i=1;i<=n;i++)
    {
        c=max(c,abs(x[i]-max_x)+abs(y[i]-max_y));
        c=max(c,abs(x[i]-max_x)+abs(y[i]-min_y));
        c=max(c,abs(x[i]-min_x)+abs(y[i]-max_y));
        c=max(c,abs(x[i]-min_x)+abs(y[i]-min_y));
    }
    cout << 2*c ;
    c=2*(max_x-min_x)+2*(max_y-min_y);
    for(int i=4;i<=n;i++)
    {
        cout << " " << c;
    }
    cout << endl ;
    return 0;
}