| Task: | Closest points |
| Sender: | aalto26jw_006 |
| Submission time: | 2026-11-11 21:25:06 +0200 |
| Language: | C++ (C++23) |
| Status: | READY |
| Result: | TIME LIMIT EXCEEDED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.00 s | details |
| #2 | TIME LIMIT EXCEEDED | -- | details |
| #3 | TIME LIMIT EXCEEDED | -- | details |
| #4 | TIME LIMIT EXCEEDED | -- | details |
| #5 | ACCEPTED | 0.00 s | details |
| #6 | TIME LIMIT EXCEEDED | -- | details |
| #7 | ACCEPTED | 0.00 s | details |
| #8 | ACCEPTED | 0.00 s | details |
| #9 | ACCEPTED | 0.00 s | details |
| #10 | TIME LIMIT EXCEEDED | -- | details |
| #11 | ACCEPTED | 0.00 s | details |
| #12 | ACCEPTED | 0.01 s | details |
| #13 | TIME LIMIT EXCEEDED | -- | details |
| #14 | ACCEPTED | 0.00 s | details |
| #15 | ACCEPTED | 0.01 s | details |
| #16 | TIME LIMIT EXCEEDED | -- | details |
| #17 | TIME LIMIT EXCEEDED | -- | details |
| #18 | ACCEPTED | 0.00 s | details |
Compiler report
input/code.cpp: In function 'int main()':
input/code.cpp:546:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
546 | for (int j = 0; j < points.size(); j++){
| ~~^~~~~~~~~~~~~~~
input/code.cpp:547:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
547 | for (int i = j+1; i < points.size(); i++){
| ~~^~~~~~~~~~~~~~~Code
#include <iostream>
#include <vector>
#include <functional>
#include <set>
#include <algorithm>
#include <stack>
#include <unordered_map>
#include <map>
#include <iomanip>
#include <limits>
#include <queue>
#include <math.h>
#include <bits/stdc++.h>
typedef long long LL;
typedef std::tuple<LL> TUP1LL;
typedef std::tuple<LL,LL> TUP2LL;
typedef std::tuple<LL,LL,LL> TUP3LL;
typedef std::tuple<LL,LL,LL,LL> TUP4LL;
std::tuple<LL> readLL1(){
LL a;
std::cin >> a;
return {a};
}
std::tuple<LL,LL> readLL2(){
LL a, b;
std::cin >> a >> b;
return {a,b};
}
std::tuple<LL,LL,LL> readLL3(){
LL a, b, c;
std::cin >> a >> b >> c;
return {a,b,c};
}
std::tuple<LL,LL,LL,LL> readLL4(){
LL a, b, c, d;
std::cin >> a >> b >> c >> d;
return {a,b,c,d};
}
std::vector<LL> readVecLL(LL n){
std::vector<LL> arr(n);
for (LL i = 0; i < n; i++){
LL a;
std::cin >> a;
arr[i] = a;
}
return arr;
}
std::string readStr(){
std::string a;
std::cin >> a;
return a;
}
std::vector<std::string> readVecStr(LL n){
std::vector<std::string> arr(n);
for (LL i = 0; i < n; i++){
std::string a;
std::cin >> a;
arr[i] = a;
}
return arr;
}
std::vector<std::tuple<LL,LL>> readVecTup2(LL n){
std::vector<std::tuple<LL,LL>> arr(n);
for (LL i = 0; i < n; i++){
arr[i] = readLL2();
}
return arr;
}
std::vector<std::tuple<LL,LL,LL>> readVecTup3(LL n){
std::vector<std::tuple<LL,LL,LL>> arr(n);
for (LL i = 0; i < n; i++){
arr[i] = readLL3();
}
return arr;
}
std::vector<std::tuple<double,double,double>> readVecTup3Dup(LL n){
std::vector<std::tuple<double,double,double>> arr(n);
for (LL i = 0; i < n; i++){
double a, b, c;
std::cin >> a;
std::cin >> b;
std::cin >> c;
arr[i] = {a,b,c};
}
return arr;
}
std::vector<std::tuple<LL,LL,LL,LL>> readVecTup4(LL n){
std::vector<std::tuple<LL,LL,LL,LL>> arr(n);
for (LL i = 0; i < n; i++){
arr[i] = readLL4();
}
return arr;
}
void printNewLine(){std::cout << "\n";}
template<typename T, typename... Ts>
std::tuple<Ts...> tail(std::tuple<T,Ts...> as){
return std::apply([](T &a, Ts... b){return std::make_tuple(b...);},as);
}
template<typename T>
void print(T a){std::cout << std::setprecision(19) << a;}
template<typename... T>
void println(T... a);
template<typename T, typename Ts>
void print(std::tuple<T,Ts> a){
print(std::get<0>(a));
print(" ");
print(std::get<1>(a));
}
template<typename T, typename... Ts>
void print(std::tuple<T,Ts...> a){
print(std::get<0>(a));
print(" ");
print(tail(a));
}
template<typename T>
void print(const std::vector<T> &arr, LL width = -1){
if (width == -1) width = arr.size();
for (LL i = 0; i < (LL)arr.size(); i++){
print(arr[i]);
if (i+1 == (LL)arr.size()) continue;
if ((i%width) == width-1) printNewLine();
if ((i%width) != width-1) print(" ");
}
}
template<typename... T>
void println(T... a){print(a...);printNewLine();}
template<typename T>
void sorted(std::vector<T> &arr){
std::sort(arr.begin(),arr.end(),[](const T &a, const T &b){ return a < b; });
}
template<typename T>
std::set<T> toSet(const std::vector<T> &vec){
std::set<T> c;
for (T a : vec){ c.emplace(a);}
return c;
}
template<typename T, typename N>
std::vector<N> map(const std::vector<T> &a, const std::function<N(T)> &transform){
std::vector<N> b(a.size());
LL i = 0;
for (T x : a){
b[i] = transform(x);
i++;
}
return b;
}
template<typename N, typename M, typename R>
std::vector<R> zip(const std::vector<N> &a, const std::vector<M> &b, const std::function<R(N,M)> &transform){
LL n = std::min(a.size(),b.size());
std::vector<R> res(n);
for (LL i = 0; i < n; i++){
res[i] = transform(a[i],b[i]);
}
return res;
}
template<typename T, typename N>
std::vector<N> convertVec(const std::vector<T> &a){
std::vector<N> b(a.size());
LL i = 0;
for (T x : a){
b[i] = x;
i++;
}
return b;
}
template<typename T>
std::vector<T> reverse(const std::vector<T> &a){
std::vector<T> b(a.size());
LL i = 0;
for (T x : a){
b[a.size()-1-i] = x;
i++;
}
return b;
}
template<typename T, typename R>
R reduce(const std::vector<T> &arr, R init, const std::function<R(const R,const T)> &transform){
R current = init;
for (LL idx = 0; idx < (LL)arr.size(); idx++){
current = transform(current,arr[idx]);
};
return current;
}
template<typename T>
T max(const std::vector<T> &arr){return reduce(arr, arr[0], static_cast<std::function<T(const T,const T)>>(static_cast<const T& (*)(const T&, const T&)>(std::max<T>)));}
template<typename T>
T min(const std::vector<T> &arr){return reduce(arr, arr[0], static_cast<std::function<T(const T,const T)>>(static_cast<const T& (*)(const T&, const T&)>(std::min<T>)));}
template<typename T>
std::function<T(const T,const T)> add(){return [](T a,T b){return a+b;};}
template<typename T>
std::function<T(const T,const T)> modAdd(T mod){return [mod](T a,T b){return (((a+b)%mod)+mod)%mod;};}
template<typename T, typename R>
std::function<R(const R,const T)> mulAdd(R mul){return [mul](R a,T b){return a+b*mul;};}
template<typename T>
T sum(const std::vector<T> &arr){return reduce(arr, 0, add<T>());}
template<typename T>
T avg(const std::vector<T> &arr){return reduce(arr, 0.0, mulAdd<double,T>(1.0/arr.size()));}
template<typename T>
T binarySearch(T min, T max, const std::function<bool(T)> &leq){
if (min == max) return max;
T guess = (min+max)/2;
if (leq(guess)){
return binarySearch(min,guess,leq);
}else{
return binarySearch(guess+1,max,leq);
}
}
template<typename T>
T binarySearchDecending(T min, T max, const std::function<bool(T)> &leq){
std::function<bool(T)> gt = [leq](T x){
return !leq(x);
};
return binarySearch(min,max+1, gt)-1;
}
template<typename T>
std::vector<T> cloneVec(std::vector<T> a){return a;}
template<typename T>
std::vector<T> padding(const std::vector<T> &initial, T num, LL start, LL end){
std::vector<T> arr(start+initial.size()+end);
for (LL i = 0; i < start; i++){
arr[i] = num;
}
for (LL i = 0; i < (LL)initial.size(); i++){
arr[start+i] = initial[i];
}
for (LL i = 0; i < end; i++){
arr[start+initial.size()+i] = num;
}
return arr;
}
template<typename T>
LL findMax(LL start, LL end, const std::function<T(LL)> &maxHeuristic){
T initialGuess = maxHeuristic(start);
LL index = start;
for (LL i = start; i <= end; i++){
if (initialGuess < maxHeuristic(i)){
initialGuess = maxHeuristic(i);
index = i;
}
}
return index;
}
template<typename T>
void operateOnMax(LL start, LL end, const std::function<T(LL)> &maxHeuristic, const std::function<void(LL)> &found){
found(findMax(start,end,maxHeuristic));
}
template<typename T>
void stackOperate(std::vector<T> init, const std::function<std::vector<T>(T)> operate){
std::stack<T> stack;
for (auto x : init){
stack.push(x);
}
while (!stack.empty()){
T next = stack.top();
stack.pop();
std::vector<T> nextSteps = operate(next);
for (T a : nextSteps){
stack.push(a);
}
}
}
template<typename T>
void queueOperate(std::vector<T> init, const std::function<std::vector<T>(T)> operate){
std::queue<T> que;
for (auto x : init){
que.push(x);
}
while (!que.empty()){
T next = que.front();
que.pop();
std::vector<T> nextSteps = operate(next);
for (T a : nextSteps){
que.push(a);
}
}
}
template<typename T>
void priorityQueueOperate(std::vector<T> init, const std::function<std::vector<T>(T)> operate){
std::priority_queue<T> que;
for (auto x : init){
que.push(x);
}
while (!que.empty()){
T next = que.top();
que.pop();
std::vector<T> nextSteps = operate(next);
for (T a : nextSteps){
que.push(a);
}
}
}
template<typename T>
void recursiveVectorSplit(LL start, LL end, LL distl, LL distr, const std::function<T(LL)> &maxHeuristic, const std::function<void(LL)> &found){
if (start == end){
return found(start);
}else if (end < start){
return;
}
std::tuple<LL,LL> range = {start,end};
std::function<std::vector<std::tuple<LL,LL>>(std::tuple<LL,LL>)> splitter = [distl, distr,&maxHeuristic,&found](std::tuple<LL,LL> range){
auto [start,end] = range;
LL idx = findMax(start, end, maxHeuristic);
found(idx);
std::vector<std::tuple<LL,LL>> next;
if (idx+distl+1 <= end){
next.push_back({idx+distl+1,end});
}
if (start <= idx-distr-1){
next.push_back({start, idx-distr-1});
}
return next;
};
stackOperate({range},splitter);
}
template<typename T>
std::vector<T> dynamicallyComputableList(LL n, std::function<T(std::vector<T>&,LL)> next){
std::vector<T> arr(n);
for (LL i = 0; i < n; i++){
arr[i] = next(arr,i);
}
return arr;
}
template<typename T>
LL indexOfBinarySearch(const std::vector<T> &arr, const T &find){
return binarySearch((LL)0,(LL)arr.size()-1,(std::function<bool(LL)>)[&arr, &find](LL guess){return find <= arr[guess];});
}
template<typename T>
std::unordered_map<T, LL> indexCompress(const std::vector<T> &arr){
std::unordered_map<T, LL> compressed;
LL i = 0;
for (T x : arr){
if (compressed.find(x) != compressed.end()) compressed[x] = i++;
}
return compressed;
}
template<typename... Ts>
std::tuple<std::vector<std::tuple<LL,Ts...>>, std::vector<LL>> edgeIndexing(int n, std::vector<std::tuple<LL,Ts...>> edges){
sorted(edges);
std::vector<LL> edgeIndex(n+1);
{
LL j = 0;
for (LL i = 0; i < (LL)edges.size(); i++) {
auto a = std::get<0>(edges[i]);
while (j <= a){
edgeIndex[j++] = i;
}
}
while (j < n){
edgeIndex[j++] = edges.size();
}
edgeIndex[n] = edges.size();
}
return {edges,edgeIndex};
}
template<typename T>
std::tuple<std::vector<T>, std::vector<LL>> shortestPathDirected(const LL n, std::vector<std::tuple<LL, LL, T>> edgesInit, LL start){
//assumes all paths are between 0 <= c < n
//assumes 0 indexing
std::vector<LL> path(n);
std::vector<bool> edgeUpdated(n);
std::vector<T> distance(n);
for (LL i = 0; i < n; i++) path[i] = i;
for (LL i = 0; i < n; i++) edgeUpdated[i] = true;
edgeUpdated[start] = false;
for (LL i = 0; i < n; i++) distance[i] = std::numeric_limits<T>::max()/4;
distance[start] = 0;
auto [edges,edgeIndex] = edgeIndexing(n,edgesInit);
std::function<std::vector<std::tuple<LL,LL>>(std::tuple<LL,LL>)> func = [&distance,&edgeIndex,&edges,&path,&edgeUpdated](std::tuple<LL,LL> propagateW){
auto& [weight,propagate] = propagateW;
std::vector<std::tuple<LL,LL>> next;
if (distance[propagate] != -weight) return next;
if (edgeUpdated[propagate]) return next;
for (LL i = edgeIndex[propagate]; i < edgeIndex[propagate+1]; i++){
auto& [a, b, w] = edges[i];
if (distance[a]+w < distance[b]){
//if (std::min(distance[a],w) > distance[b]){
next.push_back({-(distance[a]+w),b});
//next.push_back({std::min(distance[a],w),b});
distance[b] = std::min(distance[a],w);
path[b] = a;
edgeUpdated[b] = false;
}
}
edgeUpdated[propagate] = true;
return next;
};
priorityQueueOperate((std::vector<std::tuple<LL,LL>>){{0,start}},func);
//for (LL i = 0; i < n; i++) {
// bool changed = false;
// for (auto& e : edges) {
// auto& [a, b, w] = e;
// if (!changed) {changed = (distance[b] != std::min(distance[b], distance[a]+w));}
// if (distance[a]+w < distance[b]){
// distance[b] = distance[a]+w;
// path[b] = a;
// }
// }
// if (!changed) break;
// if (changed && i == n){
// return std::tuple((std::vector<T>){},(std::vector<LL>){});
// }
//}
return std::tuple(distance,path);
}
std::vector<LL> pathFromPathMap(std::vector<LL> &map, LL goal){
std::stack<LL> fullPath;
fullPath.push(goal);
while (map[fullPath.top()] != fullPath.top()){
fullPath.push(map[fullPath.top()]);
}
std::vector<LL> p;
while (!fullPath.empty()){
p.push_back(fullPath.top());
fullPath.pop();
}
return p;
}
template<typename T>
std::tuple<std::vector<T>, std::vector<LL>> shortestPath(const LL n, std::vector<std::tuple<LL, LL, T>> &edgesMessy, LL start){
std::vector<std::tuple<LL, LL, T>> edges;
for (auto e : edgesMessy){
auto [a,b,t] = e;
edges.push_back({a,b,t});
edges.push_back({b,a,t});
}
return shortestPathDirected(n, edges, start);
}
template<typename T>
std::vector<T> range(const std::vector<T> &a, LL from, LL to){
std::vector<T> b;
for (LL i = from; i < to; i++){
b.push_back(a[i]);
}
return b;
}
template<typename T>
bool forall(const std::vector<T> &a, std::function<bool(T)> &test){
bool res = true;
for (auto v : a){
res = res & test(v);
}
return res;
}
//double distance(TUP2LL x,TUP2LL y){
// return std::sqrt(std::get<0>(y)-std::get<0>(x))*(double)(std::get<0>(y)-std::get<0>(x))+(std::get<1>(y)-std::get<1>(x))*(double)(std::get<1>(y)-std::get<1>(x));
//}
//
//
//
//double force(TUP2LL current, std::vector<TUP2LL> point,std::vector<TUP4LL> points, double best){
// if (point.size() == 0 && points.size() == 0){
// return distance({0,0},current);
// }
// std::vector<TUP4LL> newPoints;
// std::vector<TUP2LL> newPoint;
// double min = 1.7976931348623157e+308;
// for (int i = 0; i < points.size(); i++){
// newPoint = point;
// auto [a,b,c,d] = points[i];
// newPoint.push_back({c,d});
// newPoints = {};
// for (int j = 0; j < points.size(); j++){
// if (j==i) continue;
// newPoints.push_back(points[j]);
// }
// double attempt = force({a,b},newPoint,newPoints,min);
// if (attempt < min) min = attempt;
// }
// for (int i = 0; i < points.size(); i++){
// newPoint = point;
// auto [a,b] = points[i];
// newPoint.push_back({c,d});
// newPoints = {};
// for (int j = 0; j < points.size(); j++){
// if (j==i) continue;
// newPoints.push_back(points[j]);
// }
// double attempt = force({a,b},newPoint,newPoints,min);
// if (attempt < min) min = attempt;
// }
//}
LL distance(TUP2LL x,TUP2LL y){
return (std::get<0>(y)-std::get<0>(x))*(std::get<0>(y)-std::get<0>(x))+(std::get<1>(y)-std::get<1>(x))*(std::get<1>(y)-std::get<1>(x));
}
LL distanceLimit(TUP2LL x,TUP2LL y){
return (std::get<0>(y)-std::get<0>(x))*(std::get<0>(y)-std::get<0>(x));
}
bool distancesort(TUP2LL x,TUP2LL y){
return distance({0,0},x)<distance({0,0},y);
}
int main() {
auto [n] = readLL1();
auto points = readVecTup2(n);
std::sort(points.begin(), points.end(), distancesort);
//sorted(points);
LL min = 7999999984000000009LL;
for (int j = 0; j < points.size(); j++){
for (int i = j+1; i < points.size(); i++){
if (min < std::sqrt(distance({0,0},points[j]))-std::sqrt(distance({0,0},points[i]))) break;
//if (min < distanceLimit(points[i],points[j])) break;
if (min < distance(points[i],points[j])) continue;
min = distance(points[i],points[j]);
}
}
println(min);
return 0;
}
Test details
Test 1
Verdict: ACCEPTED
| input |
|---|
| 100 58 36 81 -7 46 49 87 -58 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 2
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 200000 -222 -705 277 680 -436 561 528 -516 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| (empty) |
Test 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 200000 -464738043 865360844 465231470 129093134 -276549869 -21946314 111055008 -48821736 ... |
| correct output |
|---|
| 25413170 |
| user output |
|---|
| (empty) |
Test 4
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 200000 1 513001000 2 689002000 3 785003000 4 799004000 ... |
| correct output |
|---|
| 1000000 |
| user output |
|---|
| (empty) |
Test 5
Verdict: ACCEPTED
| input |
|---|
| 4 0 0 0 3 3 0 1 1 |
| correct output |
|---|
| 2 |
| user output |
|---|
| 2 |
Test 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 200000 1 0 1 1 1 2 1 3 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| (empty) |
Test 7
Verdict: ACCEPTED
| input |
|---|
| 4 1 2 10 3 3 5 8 5 |
| correct output |
|---|
| 8 |
| user output |
|---|
| 8 |
Test 8
Verdict: ACCEPTED
| input |
|---|
| 4 10 6 4 10 8 3 2 3 |
| correct output |
|---|
| 13 |
| user output |
|---|
| 13 |
Test 9
Verdict: ACCEPTED
| input |
|---|
| 2 -999999999 -999999999 999999999 999999999 |
| correct output |
|---|
| 7999999984000000008 |
| user output |
|---|
| 7999999984000000008 |
Test 10
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 200000 0 1 1 1 2 1 3 1 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| (empty) |
Test 11
Verdict: ACCEPTED
| input |
|---|
| 8 1 10000 -1 -10000 2 0 -2 0 ... |
| correct output |
|---|
| 16 |
| user output |
|---|
| 16 |
Test 12
Verdict: ACCEPTED
| input |
|---|
| 3 -1000000000 -1000000000 1000000000 1000000000 0 0 |
| correct output |
|---|
| 2000000000000000000 |
| user output |
|---|
| 2000000000000000000 |
Test 13
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 199999 1 1 2 1 3 1 4 1 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| (empty) |
Test 14
Verdict: ACCEPTED
| input |
|---|
| 4 0 0 5 8 6 1 10000 0 |
| correct output |
|---|
| 37 |
| user output |
|---|
| 37 |
Test 15
Verdict: ACCEPTED
| input |
|---|
| 435 -842 -199 -480 798 -176 -406 792 608 ... |
| correct output |
|---|
| 2 |
| user output |
|---|
| 2 |
Test 16
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 200000 1 0 1 2 1 4 1 6 ... |
| correct output |
|---|
| 4 |
| user output |
|---|
| (empty) |
Test 17
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 200000 0 1 2 1 4 1 6 1 ... |
| correct output |
|---|
| 4 |
| user output |
|---|
| (empty) |
Test 18
Verdict: ACCEPTED
| input |
|---|
| 3 -1000000000 -1000000000 1000000000 1000000000 1000000000 -1000000000 |
| correct output |
|---|
| 4000000000000000000 |
| user output |
|---|
| 4000000000000000000 |
