Created
June 19, 2017 07:47
-
-
Save anonymous/759a2038707c909b8f16820c3fe90077 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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