Codeforces Gym 100492 A(バンプ、巧みなアルゴリズム)

标题:凸包を与えて、N個の点を含んで、各点を削除してから凸包を求めて、凸包の上の点の平均値.p/qの最も単純な形式で出力され、最初はq=Nである.タイトルは、隣接する2つのエッジが平行であることを許可しないことを要求します.リンク:http://codeforces.com/gym/100492 A題
どのように见ても构想がなく、列挙して各点を削除し、その左の点から右の点までもう一度凸包を求めるという方法が考えられるかもしれません.复雑さは依然としてO(N)ですが、このように符号化するのは非常に难しく、书きやすいです.よく考えてみると、何度か凸包を必要とするだけでいいことがわかりました.まず凸包を求めて、仮に凸包に偶数の点1..nがあると仮定して、次に、2つの点ごとに間接的に遮蔽して、まず凸包に1,3,5,...n-1番の点を遮蔽して、それから凸包を求めて、この時1,3,5,...n-1番の点が削除された時の状況を表して、答えの1つを計算して、更に2,4,6,...n番の点を遮蔽して、更に1回計算して、それ以外に、また、バンプにない点を削除する場合も計算されます.3回の答えの和が最終的な答えです.バンプ上の点が奇数の場合、計算を1回追加する必要がありますが、同様です.3回または4回の計算時の計算方法に注意し、少ないか多いかを統計しないでください.
小結:この問題は方法が良ければ書きやすく、方法が悪ければ書きにくく、甚だしきに至っては「書けない」という問題で、思考の難易度が高く、コードが容易で、このタイプの問題を多く書くことは思考の向上に役立つ.

//Hello. I'm Peter.
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cctype>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const double eps = 1e-9, pi = acos(-1.0);

inline int dcmp(double x){
    if(fabs(x) < eps) return 0;
    else if(x > 0) return 1;
    else return -1;
}

struct Point{
    double x, y;
    int id;
    Point(){};
    Point(double x1, double y1){
        x = x1;
        y = y1;
    }
};
typedef Point Vector;

Vector operator - (const Vector a, const Vector b){
    return Vector(a.x - b.x, a.y - b.y);
}
double operator % (const Vector a, const Vector b){
    return a.x * b.y - a.y * b.x;
}
bool cmp1(const Point a, const Point b){
    if(dcmp(a.x - b.x) != 0) return a.x < b.x;
    else return a.y < b.y;
}

#define N 200010
int notvis[N],kase;

void ConvexHull(Point *p, int n, Point *c, int &m){
    m = 0;
    for(int i = 0; i < n; i++){
        if(notvis[p[i].id] == kase) continue;
        while(m > 1 && dcmp((c[m-1] - c[m-2]) % (p[i] - c[m-1])) <= 0) m--;
        c[m++] = p[i];
    }

    int k = m;
    for(int i = n - 2; i >= 0; i--){
        if(notvis[p[i].id] == kase) continue;
        while(m > k && dcmp((c[m-1] - c[m-2]) % (p[i] - c[m-1])) <= 0) m--;
        c[m++] = p[i];
    }

    if(m > 1) m--;
}
Point p[N], c[N], d[N];
int n, m, nd;

ll up, down;

int main(){
    freopen("average.in","r",stdin);
    freopen("average.out","w",stdout);

    n = read();
    for(int i = 0; i < n; i++){
        int x, y;
        x = read(), y = read();
        p[i] = Point(x, y);
        p[i].id = i;
        notvis[i] = 0;
    }
    sort(p, p + n, cmp1);

    kase = 1;
    ConvexHull(p, n, c, m);

    down = n;
    up = 1LL * (n - m) * m;

    if(m & 1){
        kase ++;
        for(int i = 0; i < m - 1; i += 2){
            notvis[c[i].id] = kase;
        }
        ConvexHull(p, n, d, nd);
        up += nd - ((m>>1) + 1) + 1LL * (m>>1) * (m - 1);

        kase ++;
        for(int i = 1; i < m - 1; i += 2){
            notvis[c[i].id] = kase;
        }
        ConvexHull(p, n, d, nd);
        up += nd - ((m>>1) + 1) + 1LL * (m>>1) * (m - 1);

        kase++;
        notvis[c[m-1].id] = kase;
        ConvexHull(p, n, d, nd);
        up += nd;
    }
    else{
        kase ++;
        for(int i = 0; i < m; i += 2){
            notvis[c[i].id] = kase;
        }
        ConvexHull(p, n, d, nd);
        up += nd - (m>>1) + 1LL * (m>>1) * (m - 1);

        kase ++;
        for(int i = 1; i < m; i += 2){
            notvis[c[i].id] = kase;
        }
        ConvexHull(p, n, d, nd);
        up += nd - (m>>1) + 1LL * (m>>1) * (m - 1);
    }

    ll g = __gcd(up, down);
    up /= g, down /= g;

    cout<<up<<"/"<<down<<endl;

    return 0;
}