|
|
back to boardHow to solve this problem without long arithmetic? If i use double -> big error If i use long long -> overflow now i got Runtime error on java. Where I am wrong? I think my function Less is bad but I can't find mistake. My code: import java.math.*; import java.util.*; public class BigNumbers { final int tmax=100; MathContext mc = new MathContext(tmax);
final int nmax=5005;
static int Pox[], Poy[], id[]; static BigDecimal Px[], Py[]; static int n, left;
public static boolean Less(BigDecimal x1, BigDecimal y1, BigDecimal x2, BigDecimal y2) { return (y1.compareTo(BigDecimal.ZERO)!=-1) && (y2.compareTo(BigDecimal.ZERO)==1) && ((y1.multiply(x2)).compareTo(x1.multiply(y2))==-1) || (y1.compareTo(BigDecimal.ZERO)==-1) && ((y2.compareTo(BigDecimal.ZERO)!=-1)) || ((x1.multiply(y2)).compareTo(x2.multiply(y1))==1); }
public static BigDecimal modul2(BigDecimal x, BigDecimal y) { return (x.multiply(x)).add(y.multiply(y)); }
public static void QSort(int L, int R) { int m=(L+R)/2; int i=L; int j=R;
while(i<=j) { while(Less(Px[i],Py[i],Px[m],Py[m])) i++; while(!Less(Px[j],Py[j],Px[m],Py[m]) && j!=m) j--; if(i<=j) { BigDecimal Y=Px[i]; Px[i]=Px[j]; Px[j]=Y; Y=Py[i]; Py[i]=Py[j]; Py[j]=Y; int y=id[i]; id[i]=id[j]; id[j]=y; i++; j--; } } if(L<j) QSort(L, j); if(i<R) QSort(i, R); }
public static void main(String args[]) { Scanner sc=new Scanner(System.in); n=sc.nextInt();
Pox=new int[n+1]; Poy=new int[n+1]; id=new int[n+1]; Px=new BigDecimal[n+1]; Py=new BigDecimal[n+1];
for(int i=1;i<=n;i++) { int x, y; x=sc.nextInt(); y=sc.nextInt(); Pox[i]=x; Poy[i]=y; }
System.out.println(Pox[1]+" "+Poy[1]);
for(int i=1;i<=n-1;i++) { BigDecimal x=BigDecimal.valueOf(Pox[i+1]-Pox[1]); BigDecimal y=BigDecimal.valueOf(Poy[i+1]-Poy[1]); Px[i]=x.divide(modul2(x,y)); Py[i]=y.divide(modul2(x,y)); id[i]=i+1; }
left=1; for(int i=2;i<=n-1;i++) if(Px[left].compareTo(Px[i])==1 || Px[left].compareTo(Px[i])==0 && Py[left].compareTo(Py[i])==1) left=i;
System.out.println(Pox[id[left]]+" "+Poy[id[left]]);
for(int i=1;i<=n-1;i++) { Px[i]=Px[i].subtract(Px[left]); Py[i]=Py[i].subtract(Py[left]); }
for(int i=left;i<=n-2;i++) { Px[i]=Px[i+1]; Py[i]=Py[i+1]; }
QSort(1,n-2); System.out.print(Pox[id[(n-1)/2]]+" "+Poy[id[(n-1)/2]]); } } |
|
|