# PAPER - Editorial

Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

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 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){
}
long long readIntLn(long long l,long long r){
}
}
}
int T;
int n,m;
double w,h;
string s;
double x,y;
int main(){
//freopen("06.txt","r",stdin);
//freopen("06o.txt","w",stdout);
cout<<fixed;
cout.precision(10);
while(T--){
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++){
}
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

// 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,y;
int cnt;
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;
Arrays.fill(di, ans/2);
for(int i = 0; i< m; i++){
di = Math.min(di, h-p[i]);
di = Math.min(di, p[i]);
di = Math.min(di, p[i]);
di = Math.min(di, w-p[i]);
for(int j = i+1; j< m; j++)
ans = Math.min(ans, Math.sqrt((p[i]-p[j])*(p[i]-p[j])+(p[i]-p[j])*(p[i]-p[j])));
}
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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


Feel free to share your approach. Suggestions are welcomed as always. 4 Likes

I used the same approach which is given by the setter but when i submit iam getting TLE.
Can you please tell me what is wrong in this code

I think problem is in line 7.

May i know what is the problem coz i just created a vector of pairs

Can you find any potential error in my code?

Nope …

kudos to the editorialst for such a nice explanation and kudos to the author for such nice question

1 Like

why we are taking 0 for Up, 1 for Down, 2 for Left and 3 for Right.
because when i am trying to do it with 0, 1 as Right, Left and 2,3 for Up down its giving WA.

So can anyone tell, why this operation is done?
@taran_1407

I am using the same approach as given in the editorial still getting WA please somebody help.https://www.codechef.com/viewsolution/30686732