QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#123356 | #4139. 最近最远点对 | GoatGirl98 | 100 ✓ | 53ms | 9020kb | C++14 | 4.4kb | 2023-07-12 13:18:53 | 2023-07-12 13:18:54 |
Judging History
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