THREEPTS - Editorial

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

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.
Can any one please help.

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 :neutral_face:

sahi toh hai…

Here’s my solution Solution: 49881417 | CodeChef . Hope it helps :slight_smile:

I am not able to solve it please help. Thanks in advance

Given an array with min length of 8, choose 2 groups of 2 numbers such that in each group, the two numbers must not be adjacent. Multiply the numbers in both groups and subtract one from other. Maximize this result Ex: 2,1,3,4,8,6,7,9 2 groups → 1,4 & 6,9 → Diff = 54-4 = 50