# THREEPTS - Editorial

Editorialist: Aman Dwivedi

Simple

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();
}

``````
2 Likes

Where should this fail and are there any redundancies:

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
int t;cin>>t;
while(tâ€“)
{
ll xa,ya,xb,yb,xc,yc;

`````` cin>>xa>>ya>>xb>>yb>>xc>>yc;
int ch=0;
if((xa!=xb)&&(ya!=yb))ch++;
if((xc!=xb)&&(yb!=yc))ch++;
if(((xa-xb)*(xb-xc))<0)ch++;
if(((ya-yb)*(yb-yc))<0)ch++;

if(ch>1)cout<<"NO\n";
else cout<<"YES\n";
``````

}
}

PS: It was accepted but I think somethings wrong

Can anyone help me give testcases, where my code will fail, Plz I tried to debug a lot.

``````#include<bits/stdc++.h>

#define ll long long int

#define vec vector<ll>

#define f(var,a,b) for(ll var = a ; var < b ; var++ )

#define fr(var,a,b) for(ll var = a ; var > b ; var-- )

#define fasthoja ios_base::sync_with_stdio(false); cin.tie(NULL);

#define dbg(x)               cerr<<#x<<" : "<<x<<endl;

#define dbg2(x,y)            cerr<<#x<<" : "<<x<<"  "<<#y<<" : "<<y<<endl;

using namespace std;

void att1( ll xa,ll ya,ll xb,ll yb,ll xc, ll yc ) {

// A and B ek straight line mein rahe and B and C ek straight line mein

bool a_b = false;

bool left = false, right = false, up = false, down = false;

// check for A and B

if( xa == xb || xa == yb || ya == yb ) {

a_b = true;

if( ya > yb ) down = true;

else if( ya < yb ) up = true;

else if( xa < xb ) right = true;

else if( xa > xb ) left = true;

}

bool b_c = false;

bool left_1 = false, right_1 = false, up_1 = false, down_1 = false;

// check for B and C

if( xb == xc || xb == yc || yb == yc ) {

b_c = true;

// a -> b , b -> c

if( yb > yc ) down_1 = true;

else if( yb < yc ) up_1 = true;

else if( xb < xc ) right_1 = true;

else if( xb > xc ) left_1 = true;

}

// dbg(a_b);

// dbg(b_c);

// if( a_b && b_c &&  ) cout << "YES\n";

// else cout << "NO\n";

if( left && right_1 ) cout << "NO\n";

else if( right && left_1 ) cout << "NO\n";

else if( up && down_1 ) cout << "NO\n";

else if( down && up_1 ) cout << "NO\n";

else if( a_b && b_c ) cout << "YES\n";

else cout << "NO\n";

}

int main(void){

fasthoja;

ll t; cin>>t;

while(t--){

ll xa,ya,xb,yb,xc,yc;

cin >> xa >> ya >> xb >> yb >> xc >> yc;

att1(xa,ya,xb,yb,xc,yc);

}//end of test case loop

return 0;

}
``````

I am using the property of triangle where under given conditions, one of the coordinates of B is equal to the coordinates of A or C and angle B should be obtuse.

Here is my code::
//Author :: Jitendra Singh, IIT (BHU) Varanasi
#include<bits/stdc++.h>
using namespace std;
#define fo(i,a,n) for(long long i=a; i<n; i++)
#define pb push_back
#define ll long long
#define pii pair<ll,ll>
#define inf -1000000001
#define inff 1000000001
#define eb emplace_back
#define cnu continue
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define vi std::vector
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
//_____________________________________________________________________//
void solve()
{
ll xa,xb,ya,yb,xc,yc; cin>>xa>>ya>>xb>>yb>>xc>>yc;
if((xa==xb or ya==yb or xb==xc or yb==yc)and(((xa-xc)(xa-xc)+(ya-yc)(ya-yc))>=(xb-xc)(xb-xc)+(yb-yc)(yb-yc)+(xa-xb)(xa-xb)+(ya-yb)(ya-yb)))
cout<<â€śYES\nâ€ť;
else cout<<â€śNO\nâ€ť;
}
int main()
{
fastio;
ll t; cin>>t;
while(tâ€“) solve();
}

Can anyone please tell me what is wrong in this code or which testcases are failing

``````#include <iostream>
using namespace std;

int main()
{
int t;
cin >> t;
while (t--)
{
int xa, ya, xb, yb, xc, yc;
cin >> xa >> ya >> xb >> yb >> xc >> yc;

int xMax = max(xa, xc);
int xMin = min(xa, xc);
int yMax = max(ya, yc);
int yMin = min(ya, yc);

if ((xMin <= xb and xb <= xMax) and (yMin <= yb and yb <= yMax))
{
if ((xa == xb and yb == yc) or (ya == yb and xb == xc))
{
cout << "YES" << endl;
}
else if ((xa == xb and xb == xc) or (ya == yb and yb == yc)) //If on same line
{
cout << "YES" << endl;
}
else
cout << "NO" << endl;
}
else
cout << "NO" << endl;
}
return 0;
}
``````

Hey I think my code is correct then why wrong answer? Please can you tell any test case where it is wrong?

#include<bits/stdc++.h>

#define vi vector

#define vp vector<pair<int,int>>

#define vs vector

#define vvi vector<vector>

#define pb push_back

#define ll long long

using namespace std;

int main(){

``````ios_base::sync_with_stdio(false);

cin.tie(NULL);

int t;

cin>>t;

while(t--)

{

int xa,ya,xb,yb,xc,yc;

cin>>xa>>ya>>xb>>yb>>xc>>yc;

if(xa==xb && xb==xc)

{

if((yb>ya) && (yc>yb))

{

cout<<"YES\n";

}

else  if((yb<ya) && (yc<yb))

{

cout<<"YES\n";

}

else{

cout<<"NO\n";

}

}

else if(ya==yb && yb==yc)

{

if((xb>xa) && (xc>xb))

{

cout<<"YES\n";

}

else  if((xb<xa) && (xc<xb))

{

cout<<"YES\n";

}

else{

cout<<"NO\n";

}

}

else if(xa==xb && yb==yc)

{

cout<<"YES"<<endl;

}

else if(ya==yb && xb==xc)

{

cout<<"YES"<<endl;

}

else{

cout<<"NO"<<endl;

}

}
``````

return 0;

}

Any testcase for which this code fails.

``````#include<bits/stdc++.h>
using namespace std;

#define    ll            long long
#define    all(x)        (x).begin(),(x).end()

void Solve() {
int xa, xb, xc, ya, yb, yc;
cin >> xa >> ya >> xb >> yb >> xc >> yc;

bool ok = 0;
if (xa == xb) {
if (xb == xc) {
if (yb < ya && yc < yb) ok = 1;
else if (yb > ya && yc > yb) ok = 1;
}
else if (yb == yc) ok = 1;
}
else if (ya == yb) {
if (yb == yc) {
if (xb < xa && xc < xb) ok = 1;
else if (xb > xa && xc > xb) ok = 1;
}
else if (xb == xc) ok = 1;
}

cout << (ok ? "YES" : "NO") << endl;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);  int t = 1;
cin >> t;
while (t--) Solve();
}

``````

What is th mistake in my code. It is showing WRONG ANSWER.

Why is this code giving WA.
Here it is:

``````/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef {
public static void main (String[] args) throws java.lang.Exception {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int ax = sc.nextInt();
int ay = sc.nextInt();
int bx = sc.nextInt();
int by = sc.nextInt();
int cx = sc.nextInt();
int cy = sc.nextInt();
if (((ax == bx && bx == cx && ax == cx) && ((ay < by && by < cy) || (ay > by && by > cy))) || ((ay == by && by == cy && ay == cy) && ((ax > bx && bx > cx) || (ax < bx && bx < cx)))) {
System.out.println("YES");
} else if ((ax == bx && by == cy) || (ay == by && bx == cx)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}
``````

Can Anyone suggest some cases where this gets fails.

in the authorâ€™s code for the solution of the problem ,
can someone give the test covered by the last if else

sahi toh haiâ€¦

Hereâ€™s my solution Solution: 49881417 | CodeChef . Hope it helps