Task: | Closest points |
Sender: | aalto2024k_004 |
Submission time: | 2024-11-13 16:53:39 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | RUNTIME ERROR |
test | verdict | time | |
---|---|---|---|
#1 | RUNTIME ERROR | 0.00 s | details |
#2 | RUNTIME ERROR | 0.14 s | details |
#3 | RUNTIME ERROR | 0.22 s | details |
#4 | RUNTIME ERROR | 0.18 s | details |
#5 | RUNTIME ERROR | 0.00 s | details |
#6 | RUNTIME ERROR | 0.14 s | details |
#7 | WRONG ANSWER | 0.00 s | details |
#8 | RUNTIME ERROR | 0.00 s | details |
#9 | WRONG ANSWER | 0.00 s | details |
#10 | RUNTIME ERROR | 0.13 s | details |
#11 | RUNTIME ERROR | 0.00 s | details |
#12 | WRONG ANSWER | 0.00 s | details |
#13 | RUNTIME ERROR | 0.13 s | details |
#14 | RUNTIME ERROR | 0.00 s | details |
#15 | RUNTIME ERROR | 0.00 s | details |
#16 | RUNTIME ERROR | 0.14 s | details |
#17 | RUNTIME ERROR | 0.13 s | details |
#18 | WRONG ANSWER | 0.00 s | details |
Code
#include <float.h> #include <math.h> #include <stdlib.h> #include <iostream> #include <vector> #include <iomanip> #include <algorithm> #include <climits> using namespace std; #define ll long long int struct Point { ll x, y; }; bool compareX(Point& p1, Point& p2) { return (p1.x != p2.x) ? (p1.x - p2.x) : (p1.y - p2.y); } bool compareY(Point& p1, Point& p2) { return (p1.y != p2.y) ? (p1.y - p2.y) : (p1.x - p2.x); } ll dist(Point& p1, Point& p2) { ll d = ((p1.x - p2.x) * (p1.x - p2.x)) + ((p1.y - p2.y) * (p1.y - p2.y)); //cout << d << endl; return d; } ll stripClosest(vector<Point> strip, int size, ll d) { ll min = d; for (int i = 0; i < size; ++i) for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < min; ++j) if (dist(strip[i], strip[j]) < min) min = dist(strip[i], strip[j]); return min; } ll bruteForce(vector<Point>& P) { int n = P.size(); ll min = LLONG_MAX; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (dist(P[i], P[j]) < min) min = dist(P[i], P[j]); return min; } ll closestUtil(vector<Point>& Px, vector<Point>& Py, int l, int r) { int n = r; if (n <= 3) return bruteForce(Px); int mid = n / 2; //cout << "mid -> " << mid << endl; Point midPoint = Px[l + mid]; vector<Point> Pyl(mid); vector<Point> Pyr(n - mid); int li = 0, ri = 0; for (int i = 0; i < n; i++) { if ((Py[i].x < midPoint.x || (Py[i].x == midPoint.x && Py[i].y < midPoint.y)) && li < mid) Pyl[li++] = Py[i]; else Pyr[ri++] = Py[i]; } ll dl = closestUtil(Px, Pyl, l, mid); ll dr = closestUtil(Px, Pyr, l + mid, n - mid); ll d = min(dl, dr); vector<Point> strip(n); int j = 0; for (int i = 0; i < n; i++) if (abs(Py[i].x - midPoint.x) < d) strip[j] = Py[i], j++; return stripClosest(strip, j, d); } double closest(vector<Point>& P) { int n = P.size(); vector<Point> Px(n); vector<Point> Py(n); for (int i = 0; i < n; i++) { Px[i] = P[i]; Py[i] = P[i]; } sort(Px.begin(), Px.end(), compareX); sort(Py.begin(), Py.end(), compareY); //cout << "hell" << endl; return closestUtil(Px, Py, 0, n); } int main() { int n; cin >> n; vector<Point> points(n); for (int i = 0; i < n; i++) { cin >> points[i].x; cin >> points[i].y; } cout << fixed << closest(points) << endl; return 0; }
Test details
Test 1
Verdict: RUNTIME ERROR
input |
---|
100 58 36 81 -7 46 49 87 -58 ... |
correct output |
---|
1 |
user output |
---|
(empty) |
Test 2
Verdict: RUNTIME ERROR
input |
---|
200000 -222 -705 277 680 -436 561 528 -516 ... |
correct output |
---|
1 |
user output |
---|
(empty) |
Test 3
Verdict: RUNTIME ERROR
input |
---|
200000 -464738043 865360844 465231470 129093134 -276549869 -21946314 111055008 -48821736 ... |
correct output |
---|
25413170 |
user output |
---|
(empty) |
Test 4
Verdict: RUNTIME ERROR
input |
---|
200000 1 513001000 2 689002000 3 785003000 4 799004000 ... |
correct output |
---|
1000000 |
user output |
---|
(empty) |
Test 5
Verdict: RUNTIME ERROR
input |
---|
4 0 0 0 3 3 0 1 1 |
correct output |
---|
2 |
user output |
---|
(empty) |
Error:
code: malloc.c:2617: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0)...
Test 6
Verdict: RUNTIME ERROR
input |
---|
200000 1 0 1 1 1 2 1 3 ... |
correct output |
---|
1 |
user output |
---|
(empty) |
Test 7
Verdict: WRONG ANSWER
input |
---|
4 1 2 10 3 3 5 8 5 |
correct output |
---|
8 |
user output |
---|
8.000000 |
Test 8
Verdict: RUNTIME ERROR
input |
---|
4 10 6 4 10 8 3 2 3 |
correct output |
---|
13 |
user output |
---|
(empty) |
Error:
code: malloc.c:2617: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0)...
Test 9
Verdict: WRONG ANSWER
input |
---|
2 -999999999 -999999999 999999999 999999999 |
correct output |
---|
7999999984000000008 |
user output |
---|
7999999984000000000.000000 |
Test 10
Verdict: RUNTIME ERROR
input |
---|
200000 0 1 1 1 2 1 3 1 ... |
correct output |
---|
1 |
user output |
---|
(empty) |
Test 11
Verdict: RUNTIME ERROR
input |
---|
8 1 10000 -1 -10000 2 0 -2 0 ... |
correct output |
---|
16 |
user output |
---|
(empty) |
Error:
malloc(): corrupted top size
Test 12
Verdict: WRONG ANSWER
input |
---|
3 -1000000000 -1000000000 1000000000 1000000000 0 0 |
correct output |
---|
2000000000000000000 |
user output |
---|
2000000000000000000.000000 |
Test 13
Verdict: RUNTIME ERROR
input |
---|
199999 1 1 2 1 3 1 4 1 ... |
correct output |
---|
1 |
user output |
---|
(empty) |
Test 14
Verdict: RUNTIME ERROR
input |
---|
4 0 0 5 8 6 1 10000 0 |
correct output |
---|
37 |
user output |
---|
(empty) |
Error:
code: malloc.c:2617: sysmalloc: Assertion `(old_top == initial_top (av) && old_size == 0)...
Test 15
Verdict: RUNTIME ERROR
input |
---|
435 -842 -199 -480 798 -176 -406 792 608 ... |
correct output |
---|
2 |
user output |
---|
(empty) |
Test 16
Verdict: RUNTIME ERROR
input |
---|
200000 1 0 1 2 1 4 1 6 ... |
correct output |
---|
4 |
user output |
---|
(empty) |
Test 17
Verdict: RUNTIME ERROR
input |
---|
200000 0 1 2 1 4 1 6 1 ... |
correct output |
---|
4 |
user output |
---|
(empty) |
Test 18
Verdict: WRONG ANSWER
input |
---|
3 -1000000000 -1000000000 1000000000 1000000000 1000000000 -1000000000 |
correct output |
---|
4000000000000000000 |
user output |
---|
4000000000000000000.000000 |