I made all my coordinate variables double, so I had a bug when I printed it out :( cout << (int)x << ' ' << int(y) << '\n'; -> fixed my bug 5 0 -100000000 1 -100000000 1 -99999999 -1 100000000 0 100000000 I think, this answer is wrong: 0 -100000000 1 -100000000 -1 100000000 But my AC program doesn't think so. And I still ask you to make the third test without trash in the end. Thanks for pointing out the trash in the end of 3rd test case! Всем привет! Долго пытаюсь решить задачу, не вижу никаких логических ошибок(плохо знаком с JAVA и,может быть, ошибка в реализации). Тот, кто решил, подскажите, в чём проблема. Решаю так: беру n-ю точку, произвожу инверсию относительно n-й точки (R=1). Затем ищу прямую, делящую плоскость на 2 части, чтобы в каждой части было ровно (N-3)/2 точек (кроме n-й и 2х выбранных для прямой). Выбранные 3 точки и есть ответ. Ищу прямую так (среди конечных точек): найдём самую нижнюю точку, сделаем её n-1 -й; она войдёт в ответ; перенесём СК в эту точку; затем отсортируем относительно неё (точки) оставшиеся точки и выберем из них среднюю. Почему алгоритм корректен? После инверсии имеем n-1 конечные точки и 1 бесконечную. Заметим, что нет прямой, проходящей через 3 конечные точки (если такая есть, то возможны 2 варианта: 1)прямая проходит через О - тогда при обратной инверсии она проходит через О и при этом содержит 4 точки; 2)прямая не проходит через О - тогда при обратной инверсии она перейдёт в окружность, проходящую через О, тогда эти 3 точки и бесконечная точка лежат на одной окружности). А тогда можно найти прямую, разделяющую плоскость на 2 части, в каждой из которых содержится равное число конечных точек. Одна часть полуплоскости перейдёт во внутреннюю часть окружности, другая - во внешнюю. import java.math.*; import java.util.*; public class BigNumbers { final int nmax=5005; public static BigInteger Px[], Py[], z[]; public static int n; public static boolean Equal(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2) { BigInteger A = (x1.multiply(z2)).subtract(x2.multiply(z1)); BigInteger B = (y1.multiply(z2)).subtract(y2.multiply(z1)); return (A.compareTo(BigInteger.ZERO)==0 && B.compareTo(BigInteger.ZERO)==0); } public static boolean Less(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2) //полярный угол строго меньше { if(Equal(x1,y1,z1,x2,y2,z2)) return false; if(y1.compareTo(BigInteger.ZERO)==0) return x1.compareTo(BigInteger.ZERO)==1; else { if(x1.compareTo(BigInteger.ZERO)==1) { if(x2.compareTo(BigInteger.ZERO)!=1) return true; BigInteger v=(y2.multiply(x1)).subtract(x2.multiply(y1)); return v.compareTo(BigInteger.ZERO)==1; } else { if(x1.compareTo(BigInteger.ZERO)==0) return x2.compareTo(BigInteger.ZERO)==-1; else { BigInteger v=(y2.multiply(x1)).subtract(x2.multiply(y1)); return (x2.compareTo(BigInteger.ZERO)==-1 && v.compareTo(BigInteger.ZERO)==1); } } } } public static boolean More(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2) //полярный угол строго больше { return Less(x2,y2,z2,x1,y1,z1); } public static void QSort(int L, int R) { int m=(L+R)/2; int i=L; int j=R; while(i<=j) { BigInteger xi,yi,zi,xj,yj,zj,xm,ym,zm; xm=(Px[m].multiply(z[n-1])).subtract(z[m].multiply(Px[n-1])); //здесь перемещаем СК относительно n-1 - й точки ym=(Py[m].multiply(z[n-1])).subtract(z[m].multiply(Py[n-1])); zm=z[m].multiply(z[n-1]); xi=(Px[i].multiply(z[n-1])).subtract(z[i].multiply(Px[n-1])); yi=(Py[i].multiply(z[n-1])).subtract(z[i].multiply(Py[n-1])); zi=z[i].multiply(z[n-1]); while(Less(xi,yi,zi,xm,ym,zm)) { i++; if(i<=n) { xi=(Px[i].multiply(z[n-1])).subtract(z[i].multiply(Px[n-1])); yi=(Py[i].multiply(z[n-1])).subtract(z[i].multiply(Py[n-1])); zi=z[i].multiply(z[n-1]); } } xj=(Px[j].multiply(z[n-1])).subtract(z[j].multiply(Px[n-1])); yj=(Py[j].multiply(z[n-1])).subtract(z[j].multiply(Py[n-1])); zj=z[j].multiply(z[n-1]); while(More(xj,yj,zj,xm,ym,zm)) { j--; if(j>=1) { xj=(Px[j].multiply(z[n-1])).subtract(z[j].multiply(Px[n-1])); yj=(Py[j].multiply(z[n-1])).subtract(z[j].multiply(Py[n-1])); zj=z[j].multiply(z[n-1]); } } if(i<=j) { BigInteger v; v=Px[i]; Px[i]=Px[j]; Px[j]=v; v=Py[i]; Py[i]=Py[j]; Py[j]=v; v=z[i]; z[i]=z[j]; z[j]=v; 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(); Px=new BigInteger[n+1]; Py=new BigInteger[n+1]; z=new BigInteger[n+1]; for(int i=1;i<=n;i++) { Long x, y; x=sc.nextLong(); y=sc.nextLong(); Px[i]=BigInteger.valueOf(x); Py[i]=BigInteger.valueOf(y); } for(int i=1;i<=n-1;i++) //относительно n-й точки производим инверсию { Px[i]=Px[i].subtract(Px[n]); Py[i]=Py[i].subtract(Py[n]); z[i]=(Px[i].multiply(Px[i])).add(Py[i].multiply(Py[i])); //теперь все координаты(кроме n точки) имеют вид ((xi-xn)/zi, (yi-yn)/zi) } for(int i=1;i<=n-2;i++) //ищем самую нижнюю точку-она должна стать n-1 - й { BigInteger v1=z[n-1].multiply(Py[i]); BigInteger v2=z[i].multiply(Py[n-1]); if(v1.compareTo(v2)==-1) { BigInteger v; v=Px[i]; Px[i]=Px[n-1]; Px[n-1]=v; v=Py[i]; Py[i]=Py[n-1]; Py[n-1]=v; v=z[i]; z[i]=z[n-1]; z[n-1]=v; } } QSort(1,n-2);//сортируем по полярному углу от 0 до Pi Px[n-1]=Px[n-1].add(Px[n]); //получаем начальные коорд. Py[n-1]=Py[n-1].add(Py[n]); int m = (n-1)/2; Px[m]=Px[m].add(Px[n]); Py[m]=Py[m].add(Py[n]); System.out.println(Px[n-1]+" "+Py[n-1]); System.out.println(Px[m]+" "+Py[m]); System.out.print(Px[n]+" "+Py[n]); } } Edited by author 27.01.2018 13:53 import java.math.*; import java.util.*; public class BigNumbers { final int nmax=5005;
public static BigInteger Px[], Py[], z[]; public static int n;
public static boolean Equal(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2) { BigInteger A = (x1.multiply(z2)).subtract(x2.multiply(z1)); BigInteger B = (y1.multiply(z2)).subtract(y2.multiply(z1)); return (A.compareTo(BigInteger.ZERO)==0 && B.compareTo(BigInteger.ZERO)==0); }
public static boolean Less(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2) { if(Equal(x1,y1,z1,x2,y2,z2)) return false;
if(y1.compareTo(BigInteger.ZERO)==0) return x1.compareTo(BigInteger.ZERO)==1; else { if(x1.compareTo(BigInteger.ZERO)==1) { if(x2.compareTo(BigInteger.ZERO)!=1) return true; BigInteger v=(y2.multiply(x1)).subtract(x2.multiply(y1)); return v.compareTo(BigInteger.ZERO)==1; } else { if(x1.compareTo(BigInteger.ZERO)==0) return x2.compareTo(BigInteger.ZERO)==-1; else { BigInteger v=(y2.multiply(x1)).subtract(x2.multiply(y1)); return (x2.compareTo(BigInteger.ZERO)==-1 && v.compareTo(BigInteger.ZERO)==1); } } } }
public static boolean More(BigInteger x1, BigInteger y1, BigInteger z1, BigInteger x2, BigInteger y2, BigInteger z2) { return Less(x2,y2,z2,x1,y1,z1); }
public static void QSort(int L, int R) { int m=(L+R)/2; int i=L; int j=R; while(i<=j) { BigInteger xi,yi,zi,xj,yj,zj,xm,ym,zm;
xm=(Px[m].multiply(z[n-1])).subtract(z[m].multiply(Px[n-1])); ym=(Py[m].multiply(z[n-1])).subtract(z[m].multiply(Py[n-1])); zm=z[m].multiply(z[n-1]);
xi=(Px[i].multiply(z[n-1])).subtract(z[i].multiply(Px[n-1])); yi=(Py[i].multiply(z[n-1])).subtract(z[i].multiply(Py[n-1])); zi=z[i].multiply(z[n-1]);
while(Less(xi,yi,zi,xm,ym,zm)) { i++; if(i<=n) { xi=(Px[i].multiply(z[n-1])).subtract(z[i].multiply(Px[n-1])); yi=(Py[i].multiply(z[n-1])).subtract(z[i].multiply(Py[n-1])); zi=z[i].multiply(z[n-1]); } }
xj=(Px[j].multiply(z[n-1])).subtract(z[j].multiply(Px[n-1])); yj=(Py[j].multiply(z[n-1])).subtract(z[j].multiply(Py[n-1])); zj=z[j].multiply(z[n-1]); while(More(xj,yj,zj,xm,ym,zm)) { j--; if(j>=1) { xj=(Px[j].multiply(z[n-1])).subtract(z[j].multiply(Px[n-1])); yj=(Py[j].multiply(z[n-1])).subtract(z[j].multiply(Py[n-1])); zj=z[j].multiply(z[n-1]); } }
if(i<=j) { BigInteger v; v=Px[i]; Px[i]=Px[j]; Px[j]=v; v=Py[i]; Py[i]=Py[j]; Py[j]=v; v=z[i]; z[i]=z[j]; z[j]=v; 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();
Px=new BigInteger[n+1]; Py=new BigInteger[n+1]; z=new BigInteger[n+1];
for(int i=1;i<=n;i++) { Long x, y; x=sc.nextLong(); y=sc.nextLong(); Px[i]=BigInteger.valueOf(x); Py[i]=BigInteger.valueOf(y); }
for(int i=1;i<=n-1;i++) { Px[i]=Px[i].subtract(Px[n]); Py[i]=Py[i].subtract(Py[n]); z[i]=(Px[i].multiply(Px[i])).add(Py[i].multiply(Py[i])); }
for(int i=1;i<=n-2;i++) { BigInteger v1=z[n-1].multiply(Py[i]); BigInteger v2=z[i].multiply(Py[n-1]); if(v1.compareTo(v2)==-1) { BigInteger v; v=Px[i]; Px[i]=Px[n-1]; Px[n-1]=v; v=Py[i]; Py[i]=Py[n-1]; Py[n-1]=v; v=z[i]; z[i]=z[n-1]; z[n-1]=v; } }
QSort(1,n-2);
Px[n-1]=Px[n-1].add(Px[n]); Py[n-1]=Py[n-1].add(Py[n]);
int m = (n-1)/2; Px[m]=Px[m].add(Px[n]); Py[m]=Py[m].add(Py[n]);
System.out.println(Px[n-1]+" "+Py[n-1]); System.out.println(Px[m]+" "+Py[m]); System.out.print(Px[n]+" "+Py[n]); } } 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]]); } } my program with while(n < 3) printf("there are some stupid tests!\n"); gets Output limit exceeded 3. Please, check your tests! There is some trash in the end of a file in test 3. So, my multitest found it) can you elaborate on this? czu i'm getting WA on test4. would it have to do with this? Algo which I wrote is O(n*logn) but also I know O(n) one. Try to choose one point which will be on the circle. O(1) Than try to choose another one point which will be on the circle. O(n*logn) or O(n) Finally build circle by these two points. O(n) PS: I used such two points that all other points are at one side of the line which contains these two points. I not understand why your algo is right. Maybe we'll discuss some questions by e-mail. Mine is victorbarinov@ua.fm Thanks! My simple linear solution uses Inversive geometry. 1. Inverse plane with respect to one of points (let it is A). O(n). 2. Chose another (not A) most left point (let it is B). O(n). 3. Sort all points without A and B with respect to B by polar angle and chose middle (let it is C). We want to get exactly one element on middle place, so I used std::nth_element which work O(n). 4. Output A, B, C. O(1). Thx @Ripatti [Ufa]. A solve with O(n) , got AC 0.001s. Hint for others: 1. did not need any math functions, like acos, atan. use simple vector multiplications. 2. calc cos(v[i]) , i>2. values before sorting. 3. use std::nth_element 4. if need more speed, use buffered i/o. Good Luck!! I can guarantee that the above algorithm is working. I came up with a similar algorithm :) how about the test4??? Edited by author 01.07.2009 09:47 need some hint about this test! Pls!!! Can anyone tell me what the test #2 include? Please send to my email vietlong2110@gmail.com Yes, random work. My solution ~ 0.5s. Choose three random points and count points inside circle. Maybe weak tests... Edited by author 27.01.2011 00:28 My solution resulted in Crash {FLT_INVALID_OPERATION} several times, before I understood, that the square of an integer number can be negative! Oh! What a stupid mistake!-) The crash mentioned above was caused by the following function in my source code: function Dist( const p1, p2: Point ): extended; begin Result := sqrt( sqr(p2.x-p1.x) + sqr(p2.y-p1.y) ); end; I couldn't even imagine, that sqr() function can produce negative results! So, If you get Crash on test #6, just use extended (^: Holy crap I can't believe either!! Thanks 1. there are always solutions. 2. convex polygon. but don't need to find. Edited by author 10.12.2005 05:18 Hey can you give me an idea of using convex polygons for this problem?? I solved it in O(n^2), tho it can be done in O(nlogn), but none of my solutions uses convex hulls... Can someone help me? #include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; struct Tpoint{ double x,y; }; const double eps=1e-8; const double inf=2147483647.0; int n; Tpoint p[6000]; int id[6000]; int dcmp(double x){ return x<-eps?-1:x>eps; } double cross(Tpoint p0,Tpoint p1,Tpoint p2){ double x1=p1.x-p0.x; double x2=p2.x-p0.x; double y1=p1.y-p0.y; double y2=p2.y-p0.y; return x1*y2-x2*y1; } double dot(Tpoint p0,Tpoint p1,Tpoint p2){ double x1=p1.x-p0.x; double x2=p2.x-p0.x; double y1=p1.y-p0.y; double y2=p2.y-p0.y; return x1*x2+y1*y2; } double angle(Tpoint p0,Tpoint p1,Tpoint p2){ double cr=cross(p0,p1,p2); double dt=dot(p0,p1,p2); if(!dcmp(cr)) cr=0.0; if(!dcmp(dt)) dt=0.0; return atan2(cr,dt); } bool cmp(const Tpoint& a,const Tpoint &b){ return dcmp(atan2(a.y-p[0].y,a.x-p[0].x)-atan2(b.y-p[0].y,b.x-p[0].x))<0; } bool cmp2(const int &a,const int &b){ return dcmp(angle(p[a],p[0],p[1])-angle(p[b],p[0],p[1]))<0; } void init(){ Tpoint tp; int i,j; double minx,miny; cin>>n; for(i=0;i<n;i++) cin>>p[i].x>>p[i].y; for(minx=miny=inf,i=0;i<n;i++) if(dcmp(p[i].x-minx)<0 || (dcmp(p[i].x-minx)==0 && dcmp(p[i].y-miny)<0)){ minx=p[i].x; miny=p[i].y; j=i; } tp=p[j]; p[j]=p[0]; p[0]=tp; sort(p+1,p+n,cmp); } void solve(){ int i; for(i=0;i<n;i++) id[i]=i; sort(id+2,id+n,cmp2); cout<<p[0].x<<" "<<p[0].y<<endl; cout<<p[1].x<<" "<<p[1].y<<endl; //for(i=2;i<n;i++) cout<<p[id[i]].x<<" "<<p[id[i]].y<<" "<<angle(p[id[i]],p[0],p[1])<<endl; cout<<p[id[n/2+1]].x<<" "<<p[id[n/2+1]].y<<endl; } int main(){ init(); solve(); return 0; } Me too.... BTW, are you from HNSDFZ? 1e-8 => 1e-10 then you will AC I have two solutions. The first easily gets AC, and the second passes stress test with the first but fails on the 12-th test. If you know the 12-th test or some special cases for this problem, my email is sk1@hotbox.ru. ------------------ Sergey Kopeliovich Give me some critical I/O please. I use long arithmetic, so there is no presicion error. Some new tests were added. 52 authors with inexact calculations got WA. Edited by author 24.10.2006 10:47 There was an accuracy problem in the old validator. New validator uses long arithmetics. After rejudge some WA submits turned to AC, but authors with real (not integer) numbers in output now have WA. It is ok that problem is rejudged, but it not ok to delete AC to authors which solution was previously accepted, because is server's fault, and this way we pay the damage. I think your are wrong. Admin's tester for 1103 used integer arithm and absolute correct now and found your mistake. It means that your solution gives wrong answers in some situations and, for example, may lead to crach in technical system. Therefore we must build right program despite of angry. I think administrators are wrong, because this problem has set of interesting solutions, and complication of a set of tests they reduce this problems to a writing of long real arithmetics. i think it is not good. to solve this problem you must solve problems of accuracy of calculations, instead of thinking up algorithm. Besides it is a senseless step as calculations in any case are inexact Edited by author 10.04.2007 10:16 You are wrong. My solution has a lot of float calculations and still I got AC. The calculations should be just accurate enough and you will have no problem. AC!!! time 0.4 It is very beautiful problem. I am happy, that I spent 1 hour for it. use extended thanks very very very much i wa on #10 and can't find anything wa for a long time It may be impossible to solve this problem in C++ using floating-point math because long double is double in this brain-damaged compiler. My e-mail adress is victorbarinov@ua.fm And if you know Russian, please, use it. |
|