PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Basic Geometry and Observation.
PROBLEM:
There is a paper that is folded N times, resulting in the final width of W and height H. Now, there are M points marked on its surface such that it is marked on each layer. Now the paper is unfolded. Find the distance between the closest pair of points on unfolded paper.
QUICK EXPLANATION
- The minimum distance can either be the minimum distance among any pair in the initial M points, or the distance of a point from its reflection.
- For each pair, we can manually compute distance and take the minimum. Now, for each border, we find the point nearest to that border. Say the distance is d If after unfolding, that side is chosen as the centre of some fold, then this results in the distance between a point and its clone being 2*d. We can simulate this process and also keep track of the minimum distance of current set of points from all four borders.
EXPLANATION
For sake of simplicity, forget paper and folds. You have a grid of size W*H and M points are marked on it.
Since M \leq 1000, we can consider each pair, compute distance and take minimum. We can also use faster ways to find closest pair of points as explained here, but that wasn’t necessary here.
So now, we know the smallest distance between any pair among the current M points.
Now, we need to find the distance of a pair of points, where one of the points would be the result of unfolding.
Now, suppose we unfold it to the right, as shown in the image.
Now, We can see, point C is closest to the right border. Suppose the perpendicular distance of C and right border is d. When unfolding towards the right, we can see, point C and its reflection form a pair of points with distance 2*d.
Lemma: When considering unfolding, the distance between point nearest to the border and its clone in reflection shall be minimum among all pairs of points where one point is among initial points and one point is from reflection.
Scary thoughts on how to prove
Proof: In the current example, point C and its reflection C` give the minimum distance among all pairs of points where one point is among initial points and one point is among reflection.
Let us assume point B, C and C` form a triangle. It can be easily seen that this triangle shall have an obtuse angle at point C. (Contradiction would imply C not being the point closest to the right border.) By using Sine rule, we can prove |BC`| > |CC`| thus, proving the lemma.
Hence, at all moments, we need to keep track of the distance of the closest point to each border. Whenever unfolding along a border, there would be a pair with distance twice the distance from the border.
Also, when an unfolding takes place, the closest points change. In the image, before unfolding, the point closest to right border was C, but after unfolding, the point closest to the right border becomes a clone of D, which shall have same distance from the right border as D has from the left border. The same result holds for top and bottom borders too.
This is all that is needed to solve. Just keep track of minimum distance and distance from each border to the closest point and unfold one by one.
TIME COMPLEXITY
The time complexity is O(M^2+N) per test case.
SOLUTIONS:
Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n,m;
double w,h;
string s;
double x[1111],y[1111];
int main(){
//freopen("06.txt","r",stdin);
//freopen("06o.txt","w",stdout);
cout<<fixed;
cout.precision(10);
T=readIntLn(1,50);
while(T--){
n=readIntSp(1,1000);
m=readIntSp(2,1000);
w=readIntSp(3,1000000000);
h=readIntLn(3,1000000000);
s=readStringLn(n,n);
for(int i=0;i<n;i++){
assert(s[i] =='U' || s[i] =='D' || s[i]=='L' || s[i]=='R');
}
for(int i=0;i<m;i++){
x[i]=readIntSp(1,w-1);
y[i]=readIntLn(1,h-1);
}
bool u=false,d=false,l=false,r=false;
for(int i=0;i<n;i++){
if(s[i]=='U'){
if(u){
d=true;
} else {
u=true;
}
}
if(s[i]=='D'){
if(d){
u=true;
} else {
d=true;
}
}
if(s[i]=='L'){
if(l){
r=true;
} else {
l=true;
}
}
if(s[i]=='R'){
if(r){
l=true;
} else {
r=true;
}
}
}
double sol = 2e9;
for(int i=0;i<m;i++){
if(u){
sol = min(sol, 2 * ( h-y[i]));
}
if(d){
sol = min(sol, 2 * y[i]);
}
if(r){
sol = min(sol, 2 * ( w-x[i]));
}
if(l){
sol = min(sol, 2 * x[i]);
}
}
for(int i=0;i<m;i++){
for(int j=i+1;j<m;j++){
sol = min(sol, hypot(x[i]-x[j],y[i]-y[j]));
}
}
cout<<sol<<endl;
}
assert(getchar()==-1);
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define int ll
int x[1234],y[1234];
int cnt[1234];
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,m,w,h;
cin>>n>>m>>w>>h;
string s;
cin>>s;
int i,j;
rep(i,m){
cin>>x[i]>>y[i];
}
long double mini=2e9;
mini*=1.0;
long double val;
rep(i,m){
f(j,i+1,m){
val=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
mini=min(mini,sqrt(val*1.0));
}
}
int minx=1e9,maxx=0,miny=1e9,maxy=0;
rep(i,m){
maxx=max(maxx,x[i]);
minx=min(minx,x[i]);
miny=min(miny,y[i]);
maxy=max(maxy,y[i]);
}
cnt['U']=0;
cnt['D']=0;
cnt['L']=0;
cnt['R']=0;
rep(i,s.length()){
cnt[s[i]]++;
}
if(cnt['U']>=2 || cnt['D']>=2){
cnt['U']=1;
cnt['D']=1;
}
if(cnt['L']>=2 || cnt['R']>=2){
cnt['L']=1;
cnt['R']=1;
}
if(cnt['U']){
mini=min((long double)2*(h-maxy)*1.0,mini);
}
if(cnt['D']){
mini=min((long double)2*miny*1.0,mini);
}
if(cnt['L']){
mini=min((long double)2*minx*1.0,mini);
}
if(cnt['R']){
mini=min((long double)2*(w-maxx)*1.0,mini);
}
cout<<setprecision(30)<<mini<<endl;
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class PAPER{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), m = ni();
long w = nl(), h = nl();
String s = n();
long[][] p = new long[m][];
for(int i = 0; i< m; i++)p[i] = new long[]{nl(), nl()};
double ans = Double.MAX_VALUE;
double[] di = new double[4];
Arrays.fill(di, ans/2);
for(int i = 0; i< m; i++){
di[0] = Math.min(di[0], h-p[i][1]);
di[1] = Math.min(di[1], p[i][1]);
di[2] = Math.min(di[2], p[i][0]);
di[3] = Math.min(di[3], w-p[i][0]);
for(int j = i+1; j< m; j++)
ans = Math.min(ans, Math.sqrt((p[i][0]-p[j][0])*(p[i][0]-p[j][0])+(p[i][1]-p[j][1])*(p[i][1]-p[j][1])));
}
for(int i = 0; i< n; i++){
int ch = get(s.charAt(i));
ans = Math.min(ans, 2*di[ch]);
di[ch] = di[ch^1];
}
pn(df.format(ans));
}
int get(char ch){
switch(ch){
case 'U':return 0;
case 'D':return 1;
case 'L':return 2;
case 'R':return 3;
}
return -1;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new PAPER().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 