QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#123356#4139. 最近最远点对GoatGirl98100 ✓53ms9020kbC++144.4kb2023-07-12 13:18:532023-07-12 13:18:54

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-12 13:18:54]
  • 评测
  • 测评结果:100
  • 用时:53ms
  • 内存:9020kb
  • [2023-07-12 13:18:53]
  • 提交

answer

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
const double INF = 1145141919810114514.0;
const double eps = 1e-9;
int sgn(double x)
{

    if(fabs(x) > eps)
        return x > 0 ? 1 : -1;
    else
        return 0;
}
struct point
{
    double x, y;
    point(double _x = 0.0, double _y = 0.0) : x(_x), y(_y) {}
    point operator-(const point& o) const { return point(x - o.x, y - o.y); }
    // cross product of vector 
    double operator^(const point& o) const { return x * o.y - y * o.x; }
    double dis2(const point& o) const { return (x - o.x) * (x - o.x) + (y - o.y) * (y - o.y); }
    double dis(const point& o) const { return sqrt(dis2(o)); }
    bool operator<(const point& o) const { return sgn(x - o.x) ? (sgn(x - o.x) < 0) : (sgn(y - o.y) < 0); }
};
double get_mindis(vector<point>& points)
{
    int n = (int)points.size();
    sort(points.begin(), points.end());
    function<double(int, int)> divide_and_conquer = [&](int l, int r)
    {
        if (l == r)
            return INF;
        int mi = (l + r) >> 1;
        double mi_x = points[mi].x;
        double ans = min(divide_and_conquer(l, mi), divide_and_conquer(mi + 1, r));
        int i = l, j = mi + 1;
        vector<point> tmp;

        while (i <= mi && j <= r)
            if (sgn(points[i].y - points[j].y) < 0)
                tmp.push_back(points[i]), ++i;
            else
                tmp.push_back(points[j]), ++j;
        while (i <= mi)
            tmp.push_back(points[i]), ++i;
        while (j <= r)
            tmp.push_back(points[j]), ++j;
        for (int i = l; i <= r; ++i)
            points[i] = tmp[i - l];

        tmp.clear();

        for (int i = l; i <= r; ++i)
            if ((sgn(points[i].x - (mi_x - ans)) >= 0) && (sgn(points[i].x - (mi_x + ans)) <= 0))
                tmp.push_back(points[i]);
        for (int i = 0; i < tmp.size(); ++i)
            for (int j = i - 1; (j >= 0) && (sgn(tmp[i].y - tmp[j].y - ans) <= 0); --j)
                ans = min(ans, tmp[i].dis(tmp[j]));
        return ans;
    };
    return divide_and_conquer(0, n - 1);
}
// andrew
vector<point> get_convex(vector<point>& points)
{
    int n = (int)points.size();
    sort(points.begin(), points.end());
    vector<int> stk;
    vector<bool> used(n);
    stk.push_back(0);
    // upper convex
    for (int i = 1; i < n; ++i)
    {
        while (stk.size() >= 2 && sgn((points[stk[stk.size() - 1]] - points[stk[stk.size() - 2]]) ^ (points[i] - points[stk[stk.size() - 1]])) <= 0)
            used[stk.back()] = false, stk.pop_back();
        used[i] = true, stk.push_back(i);
    }
    // stk.back() == n - 1
    // lower convex
    int upper_size = stk.size();
    for (int i = n - 2; i >= 0; --i)
    {
        if (used[i])
            continue;
        while (stk.size() > upper_size && sgn((points[stk[stk.size() - 1]] - points[stk[stk.size() - 2]]) ^ (points[i] - points[stk[stk.size() - 1]])) <= 0)
            used[stk.back()] = false, stk.pop_back();
        used[i] = true, stk.push_back(i);
    }
    // stk.back() == stk[0]
    vector<point> ret;
    for (int i = 0; i < stk.size(); ++i)
        ret.push_back(points[stk[i]]);
    return ret;
}
// Antipodal edge-point by rotating cliper O(n)
// avoid corner case (area = 0), reduce collinear points
double hull_diameter(const vector<point>& hull)
{
    int n = hull.size() - 1;
    if (n == 1)
        return 0;
    if (n == 2)
        return hull[0].dis(hull[1]);
    double ret = 0.0;
    // area of parallelogram given edges AB and BC
    function<double(const point&, const point&, const point&)> area = [&](const point&a, const point&b, const point&c)
    {
        return fabs((b - a) ^ (c - b));
    };
    int i = 0, j = 2; // edge : (i, i + 1) point : j
    
    for (; i < n; ++i)
    {
        while (sgn(area(hull[i], hull[i + 1], hull[j]) - area(hull[i], hull[i + 1], hull[(j + 1) % n])) <= 0)
            j = (j + 1) % n;
        ret = max(ret, max(hull[i].dis(hull[j]), hull[i + 1].dis(hull[j])));
    }
    return ret;
}

int main()
{
    int n;
    scanf("%d", &n);
    vector<point> points(n);
    for (int i = 0; i < n; ++i)
        scanf("%lf%lf", &points[i].x, &points[i].y);
    printf("%.2f %.2f", get_mindis(points), hull_diameter(get_convex(points)));
}

詳細信息

Test #1:

score: 10
Accepted
time: 2ms
memory: 3228kb

input:

2000
1000000000 500000005
999997532 501570798
999990130 503141576
999977793 504712324
999960522 506283024
999938316 507853663
999911176 509424224
999879102 510994693
999842094 512565052
999800153 514135288
999753280 515705384
999701474 517275325
999644736 518845096
999583066 520414680
999516467 5219...

output:

1570794.58 1000000001.28

result:

ok 2 numbers

Test #2:

score: 10
Accepted
time: 2ms
memory: 3232kb

input:

2000
1000000000 500000005
999997532 501570798
999990130 503141576
999977793 504712324
999960522 506283024
999938316 507853663
999911176 509424224
999879102 510994693
999842094 512565052
999800153 514135288
999753280 515705384
999701474 517275325
999644736 518845096
999583066 520414680
999516467 5219...

output:

1570794.58 1000000001.28

result:

ok 2 numbers

Test #3:

score: 10
Accepted
time: 2ms
memory: 3256kb

input:

2000
1000000000 500000005
999997532 501570798
999990130 503141576
999977793 504712324
999960522 506283024
999938316 507853663
999911176 509424224
999879102 510994693
999842094 512565052
999800153 514135288
999753280 515705384
999701474 517275325
999644736 518845096
999583066 520414680
999516467 5219...

output:

1570794.58 1000000001.28

result:

ok 2 numbers

Test #4:

score: 10
Accepted
time: 11ms
memory: 4196kb

input:

20000
1000000000 500000005
999999975 500157084
999999901 500314164
999999777 500471243
999999605 500628323
999999383 500785402
999999111 500942482
999998790 501099561
999998420 501256640
999998001 501413719
999997532 501570798
999997014 501727877
999996446 501884956
999995830 502042034
999995163 502...

output:

157078.32 1000000001.36

result:

ok 2 numbers

Test #5:

score: 10
Accepted
time: 8ms
memory: 4032kb

input:

20000
1000000000 500000005
999999975 500157084
999999901 500314164
999999777 500471243
999999605 500628323
999999383 500785402
999999111 500942482
999998790 501099561
999998420 501256640
999998001 501413719
999997532 501570798
999997014 501727877
999996446 501884956
999995830 502042034
999995163 502...

output:

157078.32 1000000001.36

result:

ok 2 numbers

Test #6:

score: 10
Accepted
time: 7ms
memory: 4068kb

input:

20000
1000000000 500000005
999999975 500157084
999999901 500314164
999999777 500471243
999999605 500628323
999999383 500785402
999999111 500942482
999998790 501099561
999998420 501256640
999998001 501413719
999997532 501570798
999997014 501727877
999996446 501884956
999995830 502042034
999995163 502...

output:

157078.32 1000000001.36

result:

ok 2 numbers

Test #7:

score: 10
Accepted
time: 11ms
memory: 4152kb

input:

20000
1000000000 500000005
999999975 500157084
999999901 500314164
999999777 500471243
999999605 500628323
999999383 500785402
999999111 500942482
999998790 501099561
999998420 501256640
999998001 501413719
999997532 501570798
999997014 501727877
999996446 501884956
999995830 502042034
999995163 502...

output:

157078.32 1000000001.36

result:

ok 2 numbers

Test #8:

score: 10
Accepted
time: 52ms
memory: 9020kb

input:

100000
1000000000 500000005
999999999 500031420
999999996 500062836
999999991 500094252
999999984 500125668
999999975 500157084
999999964 500188500
999999951 500219916
999999936 500251332
999999920 500282748
999999901 500314164
999999880 500345580
999999857 500376996
999999833 500408411
999999806 50...

output:

31414.63 1000000001.37

result:

ok 2 numbers

Test #9:

score: 10
Accepted
time: 49ms
memory: 8920kb

input:

100000
1000000000 500000005
999999999 500031420
999999996 500062836
999999991 500094252
999999984 500125668
999999975 500157084
999999964 500188500
999999951 500219916
999999936 500251332
999999920 500282748
999999901 500314164
999999880 500345580
999999857 500376996
999999833 500408411
999999806 50...

output:

31414.63 1000000001.37

result:

ok 2 numbers

Test #10:

score: 10
Accepted
time: 53ms
memory: 9008kb

input:

100000
1000000000 500000005
999999999 500031420
999999996 500062836
999999991 500094252
999999984 500125668
999999975 500157084
999999964 500188500
999999951 500219916
999999936 500251332
999999920 500282748
999999901 500314164
999999880 500345580
999999857 500376996
999999833 500408411
999999806 50...

output:

31414.63 1000000001.37

result:

ok 2 numbers