PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Soumyadeep Pal
Tester : Radoslav Dimitrov
Editorialist: Aman Dwivedi
DIFFICULTY:
Simple
PREREQUISITES:
Observation
PROBLEM:
There are three distinct points - A, B, C in the X-Y plane. Initially, you are located at point A. You want to reach the point C satisfying the following conditions:
- You have to go through point B.
- You can move in any of the four axis-parallel directions (+X, -X, +Y, -Y direction). However, you can make at most one turn in the path from A to C.
Determine if it is possible to reach the destination C satisfying the above conditions.
EXPLANATION:
Let us see when it is possible to reach poin C satisfying all the conditions:
Claim 1: Point B should lie between point A and point C
Proof
Let us prove this by contradiction. Suppose we have co-ordiantes of point B as (x_B, y_B) such that x_B doesn’t lies bewteen x_A and x_C. Similarly y_B doesn’t lies between y_A and y_C.
Now let’s see what will happen for co-ordinate x_B :
First we start from co-ordinate x_A and can reach to co-ordinate x_B without any turn. But after reaching co-ordinate x_B we need to go to co-ordinate x_C, for that we need to change our direction by 180 ^ \circ which is not allowed. Hence we need 2 turns of 90 ^ \circ to reach to point x_C from x_B
Similarly we can see for the y co-ordinate. Hence if point B doesn’t lies between point A and point C then it would pe never possible to reach point C satisfying all the conditions.
Now if the above condition is satisfied then there one more condition should be satisfied:
Claim 2: Atleast one of the co-ordinate of point B should be equal to the respective co-ordinate of point A or point C
Proof
Let us again prove this by contradiction. Suppose we have co-ordiantes of point B as (x_B, y_B) such that x_B is neither equal to x_A nor x_C. Similarly y_B is neither equal to y_A nor y_C.
-
To reach from point A to point B we need exactly one turn of 90 ^ \circ. As we can reach to co-ordinate x_B from co-ordinate x_A without any turn, but then we need to change our direction to reach to co-ordinate y_B.
-
Similary we need exactly one turn of 90 ^ \circ to reach point C from point A.
Hence there should be atleast one of the co-ordinate of point B should be equal to the respective co-ordinate of point A or point C
If both the conditions are satisfied then only it is possible to reach the condition C satisfying the all conditions.
TIME COMPLEXITY:
O(1) per test case
SOLUTIONS:
Author
#include<bits/stdc++.h>
using namespace std;
void solve() {
int x1, y1, x2, y2, x3, y3;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
if (x1 == x3) {
if (x2 == x1 && max(y1, y3) > y2 && y2 > min(y1, y3)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
return;
}
if (y1 == y3) {
if (y2 == y1 && max(x1, x3) > x2 && x2 > min(x1, x3)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
return;
}
if (x2 >= min(x1, x3) && max(x1, x3) >= x2 && y2 >= min(y1, y3) && max(y1, y3) >= y2 && (x2 == x1 || x2 == x3 || y2 == y1 || y2 == y3)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
solve();
}
return 0;
}
Tester
def solve_case():
x1, y1 = [int(x) for x in input().split()]
x2, y2 = [int(x) for x in input().split()]
x3, y3 = [int(x) for x in input().split()]
if x1 > x3:
x1, x3 = x3, x1
if y1 > y3:
y1, y3 = y3, y1
if x1 == x3:
if x1 == x2 and y1 < y2 < y3:
print("YES")
else:
print("NO")
elif y1 == y3:
if y1 == y2 and x1 < x2 < x3:
print("YES")
else:
print("NO")
else:
if x1 <= x2 <= x3 and y1 <= y2 <= y3 and (x1 == x2 or x2 == x3 or y1 == y2 or y2 == y3):
print("YES")
else:
print("NO")
cases = int(input())
for _ in range(cases):
solve_case()
Editorialist
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int x1,x2,x3,y1,y2,y3;
cin>>x1>>y1>>x2>>y2>>x3>>y3;
int left = min(x1,x3);
int right = max(x1,x3);
int top = max(y1,y3);
int bot = min(y1,y3);
if(x2>=left && x2<=right && (y2==top || y2==bot))
{
cout<<"Yes"<<endl;
return;
}
if(y2>=bot && y2<=top && (x2==left || x2==right))
{
cout<<"Yes"<<endl;
return;
}
cout<<"NO"<<endl;
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t;
cin>>t;
while(t--)
solve();
}