Skip to content

Instantly share code, notes, and snippets.

Created Jun 19, 2017
Embed
What would you like to do?
import java.io.*;
import java.util.*;
class ADADET
{
public static void main(String args[])throws IOException
{
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
int T=Integer.parseInt(br.readLine());
for(int b=1; b<=T; b++)
{
int n=Integer.parseInt(br.readLine());
double X[]=new double[n];
double H[]=new double[n];
for(int i=0; i<n; i++)
{
StringTokenizer s = new StringTokenizer(br.readLine());
X[i] = Double.parseDouble(s.nextToken());
H[i] = Double.parseDouble(s.nextToken());
}
for(int i=0; i<n-1; i++)
{
int d=-1;
for(int j=i+1; j<n; j++)
{
if(H[i]>H[j])
{
for(int k=i+1; k<=j; k++)
{
double t=equation(X[i],H[i],X[j],H[j],X[k]);
if((H[k]-t)<=0.0)
d=k+1;
else
k=j+1;
}
}
else
j=n;
}
System.out.print(d+" ");
}
System.out.print("-1");
}
}
public static double equation(double a, double b, double c, double d, double e)
{
double m=((d-b)/(c-a));
return (m*(e-c))+d;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment