PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Srikkanth R
Tester: Harris Leung
Editorialist: Aman Dwivedi
DIFFICULTY:
Easy
PREREQUISITES:
Observation
PROBLEM:
The manhattan distance between two points P_1(x_1, y_1) and P_2(x_2, y_2) is given by d(P_1, P_2) = |x_2 - x_1| + |y_2 - y_1|.
In other words, manhattan distance is the minimum number of moves required to reach P_2 from P_1 if, in each move, you are allowed to travel one unit along the X-axis or one unit along the Y-axis.
You are given an integer D. Find four points (P_1, P_2, P_3, P_4) with integer coordinates, such that:
- The absolute value of both X and Y coordinates of all points is at most 10^9.
- The manhattan distance between any pair of points is D .
EXPLANATION:
There are two cases:
- When D is odd.
In this case, there doesn’t exist any solution which satisfies all the given conditions.
- When D is even.
Suppose we say there are two points P(x_1, y_1) and P_2(x_2,y_2) whose manhattan distance is D.
Now what can be the third point P_3(x_3,y_3) such that the distance of this point from both the points P_1 and P_2 is D. One way of doing so is intercahnge the x and y coordinates to form a new point. Let’s say P_3(x_3,y_3) = P_2(y_2,x_2).
Now in order to satisfy the conditions of the given problem the distance between |x_1-x_2| needs to be the same as that of |y_1-y_2|. Then only when we interchange x and y coordinates of P_2 to form a point P_3.
Hence the distance D = |x_1-x_2| + |y_1-y_2| needed to be even.
Hence the distance between point P_1 and P_3 is again D. What about the distance between P_2 and P_3. How can we make sure that this distance is also D?
Let’s look, the distance between P_3 and P_2 is just the twice the distance between there x and y coordinates i.e
Hence we can say that |x_2 - y_2| = D/2. In this way, we can ensure that distance between P_3 and P_2 is also D.
What about point P_4. Just do the same interchange the x and y coordinates of point P_1. Hence in this way, we can get our four points, where the distance between any pair is D.
In simple terms the points can be written as:
TIME COMPLEXITY:
O(1) per case
SOLUTIONS:
Author
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cstdio>
#include<map>
#include<set>
#include<utility>
#include<algorithm>
#include<queue>
#include<cstdlib>
using namespace std;
// - - - - - - Data Types - - - - - - //
#define SF1(A) scanf("%d", &A)
#define SF2(A,B) scanf("%d %d", &A, &B)
#define SF3(A,B,C) scanf("%d %d %d", &A, &B, &C)
typedef long long int LLI;
typedef unsigned long long int ULL;
#define SL1(A) scanf("%lld", &A)
#define SL2(A,B) scanf("%lld %lld", &A, &B)
#define SL3(A,B,C) scanf("%lld %lld %lld", &A, &B, &C)
#define SD1(A) scanf("%lf", &A)
#define SD2(A,B) scanf("%lf %lf", &A, &B)
#define SD3(A,B,C) scanf("%lf %lf %lf", &A, &B, &C)
// - - - - - - Vectors - - - - - - //
typedef vector<int> VI;
typedef vector<LLI> VLLI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VS> VVS;
#define scanVI(V, N) for(int I=0; I<N; I++){ int X; SF1(X); V.PB(X); }
#define scanVLLI(V, N) for(int I=0; I<N; I++){ LLI X; SL1(X); V.PB(X); }
#define scanVS(V, N) for(int I=0; I<N; I++){ string X; cin >> X; V.PB(X); }
#define scanVD(V, N) for(int I=0; I<N; I++){ double X; SD1(X); V.PB(X); }
// - - - - - - Maps - - - - - - //
typedef map<int, int> MII;
typedef map<int, string> MIS;
typedef map<int, char> MIC;
typedef map<string, int> MSI;
typedef map<char, int> MCI;
typedef map<int, VI> MIVI;
// - - - - - - Pairs - - - - - - //
typedef pair<int, int> PII;
typedef pair<string, string> PSS;
typedef pair<char, char> PCC;
typedef pair<int, string> PIS;
typedef pair<int, char> PIC;
typedef pair<string, char> PSC;
typedef pair<LLI, LLI> PLL;
// - - - - - - Sets - - - - - - //
typedef set<int> SI;
typedef set<LLI> SLLI;
typedef set<string> SS;
typedef set<char> SC;
// - - - - - - - - - - - - - - - - - - //
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
clock_t Start;
inline void runTime(){
#ifdef gHost
fprintf(stderr, "\n>>Runtime: %.10f sec\n", (double) (clock() - Start) / CLOCKS_PER_SEC);
#endif
}
#define TIMER runTime();
#define PF printf
#define SF scanf
#define PB push_back
#define SR(N) right<<setw(N)
#define SL(N) left<<setw(N)
#define PREC(N) fixed << setprecision(N)
#define RJUST(N, C) right<<setw(N)<<setfill(C)
#define LJUST(N, C) left<<setw(N)<<setfill(C)
#define POP pop_back()
#define PP prev_permutation
#define NP next_permutation
#define MP make_pair
#define CLRN(A) memset(A, -1, sizeof(A))
#define CLR(A) memset(A, 0, sizeof(A))
#define BitCount(A) __builtin_popcount(A)
#define ALL(A) A.begin(), A.end()
#define ALLN(A, N) (A, A+N)
#define BSRCN(A, N, X) binary_search(ALLN(A, N), X)
#define BSRC(A, Z) binary_search(ALL(A), Z)
#define UNQ(V) sort(ALL(V)),(V).resize(unique(ALL(V))-V.begin())
#define MAX 100007
#define IMAX INT_MAX
#define LMAX 2000000000000000000LL
#define MIN -10000007
#define PI acos(-1)
#define BR puts("")
#define FastIO { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
#define READ() freopen("input.txt", "r", stdin)
#define WRITE() freopen("output.txt", "w", stdout)
#define IO READ(); WRITE();
#define SEED srand((rand()-time(NULL)))
#define ran() (((((1ULL*rand())<<31)|(1ULL*rand()))<<13)^((((1ULL*rand())<<32)|(1ULL*rand()))))
#define rran(A, B) ((ran() % ((B) - (A) + 1)) + (A))
#define SZE(A) (int)A.size()
#define CASES(T) for(int TC=1; TC<=T; TC++)
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - //
/*----------------------Graph Moves----------------*/
int ROW[]={+1,-1,+0,+0};
int COL[]={+0,+0,+1,-1};
int X[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
int Y[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
int KX[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
int KY[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
VI basePrime={1009, 1013, 1019, 1021, 1031, 1223, 1229, 1231, 1237, 1249, 1289, 1291, 1297, 1301, 1303, 353, 359, 367, 373, 379, 859, 863, 877, 881, 883,
1931, 1933, 1949, 1951, 1973, 401, 409, 419, 421, 431, 1709, 1721, 1723, 1733, 1741, 3499, 3511, 3517, 3527, 3529, 929, 937, 941, 947, 953};
/*----------------------------------------------------------------------------------------------------------------------------------------------*/
template<class XXX> XXX GCD(XXX a, XXX b) { return b == 0 ? a : GCD(b , a % b); }
template<class XXX> XXX LCM(XXX a, XXX b) { return a * (b/GCD(a, b)); }
template <class T> inline void fastRead(T &r){
r=0; register int f=1; register char ch=getchar();
while (ch<'0' or ch>'9'){f=(ch=='-'?-1:1), ch=getchar();}
while (ch>='0' and ch<='9'){r=r*10+ch-'0', ch=getchar();}
r*=f;
}
template<class XXX> inline XXX moduler(XXX num, XXX mod) {return (num>=mod?num-=mod:num);}
/// BITMASK
inline int Set(int pos, int N){return N=N | (1<<pos);}
inline int Reset(int pos, int N){return N= N & ~(1<<pos);}
inline bool Check(int pos, int N){return (bool)(N & (1<<pos));}
inline void OPFILE(){
#ifdef gHost
Start=clock();
freopen("D:\\OneDrive - Daffodil International University\\Programming\\CPP\\input.txt", "r", stdin);
freopen("D:\\OneDrive - Daffodil International University\\Programming\\CPP\\output.txt", "w", stdout);
#endif
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - END - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - //
int main()
{
OPFILE();
int d; cin >> d;
if(d%2)
{
cout << -1 << endl;
return 0;
}
cout << "0 " << d/2 << endl;
cout << d/2 << " 0" << endl;
cout << d/2 << ' ' << d << endl;
cout << d << ' ' << d/2 << endl;
TIMER;
}
Tester
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=1e5+1;
int n;
ll pf[N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin >> n;
if(n%2==1){
cout << "-1\n";
}
else{
n/=2;
cout << 0 << ' ' << n << '\n';
cout << 0 << ' ' << -n << '\n';
cout << n << ' ' << 0 << '\n';
cout << -n << ' ' << 0 << '\n';
}
//solve();
}
Editorialist
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int d;
cin>>d;
if(d%2!=0) {
cout<<-1<<"\n";
} else {
cout<<1<<" "<<1+d/2<<"\n";
cout<<1+d/2<<" "<<1<<"\n";
cout<<1+d/2<<" "<<1+d<<"\n";
cout<<d+1<<" "<<1+d/2<<"\n";
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
t=1;
while(t--)
solve();
return 0;
}