import java.util.*;
class CodeChef
{
static class Point
{
int x;
int y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
public Point(Point X){
this.x = X.x;
this.y = X.y;
}
public String toString(){
return ("x: "+x+" y: "+y);
}
boolean isEqual(Point b){
return (this.x == b.x && this.y == b.y);
}
};
static boolean onSegment(Point p, Point q, Point r)
{
if (q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) &&
q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y))
return true;
return false;
}
static int orientation(Point p, Point q, Point r)
{
if(r == null)
return -1;
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; // colinear
return (val > 0)? 1: 2; // clock or counterclock wise
}
// The main function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
static boolean doIntersect(Point p1, Point q1, Point p2, Point q2)
{
// Find the four orientations needed for general and
// special cases
int o1 = orientation(p1, q1, p2);
int o2 = orientation(p1, q1, q2);
int o3 = orientation(p2, q2, p1);
int o4 = orientation(p2, q2, q1);
// General case
if (o1 != o2 && o3 != o4)
return true;
if (o1 == 0 && onSegment(p1, p2, q1)) return true;
if (o2 == 0 && onSegment(p1, q2, q1)) return true;
if (o3 == 0 && onSegment(p2, p1, q2)) return true;
if (o4 == 0 && onSegment(p2, q1, q2)) return true;
return false;
}
// Driver code
public static void main(String[] args)
{
Scanner in= new Scanner(System.in);
int test=in.nextInt();
while(test-- >0){
int n=in.nextInt(), q=in.nextInt();
int N[]= new int[n];
int Q[]= new int[q];
for(int i=0;i<n;i++)
N[i]=in.nextInt();
for(int i=0;i<q;i++){
int x1= in.nextInt();
int x2= in.nextInt();
int y1= in.nextInt();
Point qa= new Point(x1, y1);
Point qb= new Point(x2, y1);
int c=0;
Point temp=null;
for(int j=0;j<n-1;j++){
Point p3= new Point(j+1, N[j]);
Point q3= new Point(j+2, N[j+1]);
if(qb.isEqual(p3) || q1.isEqual(q3))
continue;
System.out.println(p3.toString()+" "+q3.toString());
if(doIntersect(qa, qb, p3, q3)){
// if(orientation(qa, qb, temp)==0){
// temp=new Point(q3);
// continue;
// }
c++;
System.out.println("---> "+p3.toString()+" "+q3.toString());
// temp= new Point(q3);
}
}
System.out.println(c);
}
}
}
}
I cannot find the test case for which it is failing. It is a question from March Long Challenge. LAZER
and 