ABC 22 D - Big Bang ( Geometry, Centroid )

http://abc022.contest.atcoder.jp/tasks/abc022_d
Problem Statement: Given n ≤ 1e5 points in a 2D plane, it is then rotated, moved by the whole picture, and enlarged p times from its center. Find p.
There are a few ways to solve this problem, such as finding their longest distance in any pair of points, perimeter of convex hull, but the best way is to find the centroid of the whole graph and its maximum / minimum distance, which is O( n ).

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXABSA = 1e4 + 4;
const int MAXABSB = 1e9 + 9;

template <class T>
void upmax(T &x, T v){ if( x < v ) x = v; }

double euDis(double x0, double y0, double x1, double y1){
    double dx = fabs( x1 - x0 );
    double dy = fabs( y1 - y0 );
    return sqrt( dx * dx + dy * dy );
}

int n;

struct Point{
    double x, y;
    Point(double _x = 0, double _y = 0): x(_x), y(_y){}
} a[ MAXN ], b[ MAXN ];

void solve(){
    double agx = 0.0, agy = 0.0; // centroid coordinate
    for(int i = 0; i < n; ++i)
        agx += a[ i ].x,
        agy += a[ i ].y;
    agx /= n, agy /= n;
    double a_max_dis = 0.0;
    for(int i = 0; i < n; ++i)
        upmax( a_max_dis, euDis( agx, agy, a[ i ].x, a[ i ].y ) );

    double bgx = 0.0, bgy = 0.0;
    for(int i = 0; i < n; ++i)
        bgx += b[ i ].x,
        bgy += b[ i ].y;
    bgx /= n, bgy /= n;
    double b_max_dis = 0.0;
    for(int i = 0; i < n; ++i)
        upmax( b_max_dis, euDis( bgx, bgy, b[ i ].x, b[ i ].y ) );

    double ans = b_max_dis / a_max_dis;
    printf("%.10lf\n", ans);
}

int main(){
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[ i ].x >> a[ i ].y;
    for(int i = 0; i < n; ++i)
        cin >> b[ i ].x >> b[ i ].y;
    solve();
    return 0;
}

一応Convex Hull も書いた。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXA = 1e4 + 4;
const int MAXB = 1e9 + 9;

double euDis(double x0, double y0, double x1, double y1){
    double dx = fabs( x1 - x0 );
    double dy = fabs( y1 - y0 );
    return sqrt( dx * dx + dy * dy );
}

struct Point{
    double x, y;
    Point(double _x = 0.0, double _y = 0.0): x(_x), y(_y){}
    bool operator < (const Point &oth) const{
        if( x != oth.x ) return x < oth.x;
        return y < oth.y;
    }
    Point operator - (const Point &oth) const{
        return Point( x - oth.x, y - oth.y );
    }
    bool operator == (const Point &oth) const{
        return x == oth.x && y == oth.y;
    }
} a[ MAXN ], b[ MAXN ];

bool isBad(Point a, Point b, Point c){
    Point ab = b - a;
    Point ac = c - a;
    return ab.x * ac.y - ab.y * ac.x < 0;
}

double perimeterCH(Point *p, int n){
    sort( p, p + n );
    n = unique( p, p + n ) - p;
    vector<Point> vp;
    for(int i = 0; i < n; ++i){
        while( vp.size() >= 2 && isBad( vp[ vp.size() - 2 ], vp[ vp.size() - 1 ], p[ i ] ) )
            vp.pop_back();
        vp.push_back( p[ i ] );
    }
    int k = vp.size();
    for(int i = n - 2; i >= 0; --i){
        while( vp.size() > k && isBad( vp[ vp.size() - 2 ], vp[ vp.size() - 1 ], p[ i ] ) )
            vp.pop_back();
        vp.push_back( p[ i ] );
    }
    double res = 0.0;
    for(int i = 0; i < vp.size() - 1; ++i)
        res += euDis( vp[ i ].x, vp[ i ].y, vp[ i + 1 ].x, vp[ i + 1 ].y );
    return res;
}

int n;

void solve(){
    double pa = perimeterCH( a, n );
    double pb = perimeterCH( b, n );
    printf("%.10lf\n", pb / pa);
}

int main(){
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[ i ].x >> a[ i ].y;
    for(int i = 0; i < n; ++i)
        cin >> b[ i ].x >> b[ i ].y;
    solve();
    return 0;
}