PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Vlad
Tester: Yash Chandnani
Editorialist: Michael Nematollahi
DIFFICULTY:
EASY
PREREQUISITES:
None
PROBLEM:
You are given three sets of points A, B, C \in \R^2. You’re also given a point p represented by its coordinates x and y.
You want to choose three points a \in A, b \in B, c \in C, start from p, visit a and b in any order and then visit c. Your goal is to make the total distance travelled minimum.
QUICK EXPLANATION:
For each point in A and B, find out what’s the distance to the closest point in C to this point.
Then, try all possible combinations of a point a \in A and a point b \in B. The optimal point to choose from C is the closest point to a or b depending on the order you’ve visited them.
You’ve already calculated the distance to this optimal point, so you can access it in O(1).
EXPLANATION:
We’ll solve this problem in two steps.
Step 1:
Let a_i be a point in A. We can find the closest point c \in C to a_i by looping through all elements of C and calculating the distance between a_i and this point.
This would take O(N \times K \times log(MAX)) (where MAX = 2 \times 10^{18} is the maximum value of the square of the distance between two points), as we’re doing this for every point in A. The log factor comes from the sqrt function required to calculate a distance.
Let best[0][a_i] denote the distance between c to a_i.
Similarly, we can calculate best[1][b_i], which represents the smallest distance from a point in C to b_i. This would take O(M \times K \times log(MAX)).
Step 2:
Without loss of generality, let’s assume we first visit a point in A, then a point in B and finally a point in C.
Let’s try all the possible combination of a point a \in A and a point b \in B. For a fixed pair of a and b, the resulting total distance travelled will be
dist(p, a) + dist(a, b) + dist(b, c)
where dist(u, v) is the euclidean distance between the points u and v and c is a point in C.
Note that the first two terms are fixed as a and b are fixed. The only part that is not known is dist(b, c). To make this distance minimum, we want dist(b, c) to be minimum.
On the other hand, we’ve already calculated best[1][b] in step 1, which is the minimum value of dist(b, c) for all possible c's.
Hence, we can use best[1][b] to find the minimum value of dist(p, a) + dist(a, b) + dist(b, c) in O(log(MAX)).
This gives us a complexity of O(N \times M \times log(MAX) for step 2.
This gives us a solution with the overall complexity of O((N \times M + N \times K + M \times K) \times log(MAX)).
To see an implementation of the described solution, refer to the editorialist’s code below.
SOLUTIONS:
Setter's Solution
// OK
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
ld dist(int x1,int y1,int x2,int y2)
{
ld dx=abs(x1-x2);
ld dy=abs(y1-y2);
return sqrt(dx*dx+dy*dy);
}
const int N=5010;
const ld INF=1e10;
int a[N],b[N],c[N],d[N],e[N],f[N];
ld ab1[N],ab2[N],cd1[N],cd2[N];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int q;
cin>>q;
while(q--)
{
int x,y,n,m,k;
cin>>x>>y>>n>>m>>k;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
for(int j=1;j<=m;j++)
cin>>c[j]>>d[j];
for(int t=1;t<=k;t++)
cin>>e[t]>>f[t];
for(int i=1;i<=n;i++)
{
ab1[i]=dist(x,y,a[i],b[i]);
ab2[i]=INF;
for(int t=1;t<=k;t++)
ab2[i]=min(ab2[i],dist(a[i],b[i],e[t],f[t]));
}
for(int j=1;j<=m;j++)
{
cd1[j]=dist(x,y,c[j],d[j]);
cd2[j]=INF;
for(int t=1;t<=k;t++)
cd2[j]=min(cd2[j],dist(c[j],d[j],e[t],f[t]));
}
ld ans=INF;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=min({ans,
ab1[i]+dist(a[i],b[i],c[j],d[j])+cd2[j],
cd1[j]+dist(c[j],d[j],a[i],b[i])+ab2[i]});
cout<<fixed<<setprecision(10)<<ans<<"\n";
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void pre(){
}
int sum = 0;
ld dist(pii x,pii y){
x.fst-=y.fst,x.snd-=y.snd;
return sqrt(1ll*x.fst*x.fst+1ll*x.snd*x.snd);
}
void solve(){
int x,y,n,m,k;
scanf("%d %d\n",&x,&y);
scanf("%d %d %d\n",&n,&m,&k);
assert(x>=0&&y>=0&&x<=1e9&&y<=1e9);
assert(min({n,m,k})>=1&&max({n,m,k})<=5000);
sum+=n+m+k;
assert(sum<=15000);
vector<pii> v[3];
rep(i,n){
int a,b;scanf("%d %d\n",&a,&b);
assert(min(a,b)>=0&&max(a,b)<=1e9);
v[0].pb({a,b});
}
rep(i,m){
int a,b;scanf("%d %d\n",&a,&b);
assert(min(a,b)>=0&&max(a,b)<=1e9);
v[1].pb({a,b});
}
rep(i,k){
int a,b;scanf("%d %d\n",&a,&b);
assert(min(a,b)>=0&&max(a,b)<=1e9);
v[2].pb({a,b});
}
vector<ld> v0,v1,v2;
rep(i,n){
ld cur = 4e9;
rep(j,m){
cur = min(cur,dist(v[0][i],v[1][j])+dist(mp(x,y),v[1][j]));
}
v0.pb(cur);
}
rep(j,m){
ld cur = 4e9;
rep(i,n){
cur = min(cur,dist(v[0][i],v[1][j])+dist(mp(x,y),v[0][i]));
}
v1.pb(cur);
}
ld ans = 1e10;
rep(i,k){
rep(j,m){
ans = min(ans,dist(v[2][i],v[1][j])+v1[j]);
}
rep(j,n){
ans = min(ans,dist(v[2][i],v[0][j])+v0[j]);
}
}
cout<<setprecision(20)<<ans<<'\n';
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
pre();
int q;
scanf("%d\n",&q);
assert(q>=1&&q<=5000);
rep(i,q) solve();
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
#define F first
#define S second
const int MAXN = 5e3 + 10;
int n[3];
pii p[3][MAXN];
ld best[2][MAXN];
ld dist(pii a, pii b){
return sqrt(1ll*(a.F-b.F)*(a.F-b.F) + 1ll*(a.S-b.S)*(a.S-b.S));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(12);
int te; cin >> te;
while (te--){
int x, y; cin >> x >> y;
cin >> n[0] >> n[1] >> n[2];
for (int w = 0; w < 3; w++)
for (int i = 0; i < n[w]; i++)
cin >> p[w][i].F >> p[w][i].S;
for (int w = 0; w < 2; w++)
for (int i = 0; i < n[w]; i++) {
best[w][i] = 3e18;
for (int j = 0; j < n[2]; j++)
best[w][i] = min(best[w][i], dist(p[w][i], p[2][j]));
}
ld ans = 1e18;
for (int i = 0; i < n[0]; i++)
for (int j = 0; j < n[1]; j++)
ans = min({ans, dist({x, y}, p[0][i])
+ dist(p[0][i], p[1][j])
+ best[1][j],
dist({x, y}, p[1][j])
+ dist(p[1][j], p[0][i])
+ best[0][i]});
cout << ans << "\n";
}
return 0;
}