Show all threads Hide all threads Show all messages Hide all messages | why WA? | Diac Paul | 1207. Median on the Plane | 26 Jul 2009 18:52 | 2 | why WA? Diac Paul 15 May 2004 15:21 Can anyoane give me a nafty test? not a big one, sa I could debug it if my program gives a WA. I think it's good but I got a WA on test 2...
Me too! How did you deal with it? | qsort+Computational geometry | bobchennan | 1207. Median on the Plane | 22 May 2009 11:32 | 1 | | Now I have WA#7! | BlackShark | 1207. Median on the Plane | 22 Apr 2009 16:29 | 3 | var i,j,n,b2,n0,mid:integer; x,y,al:array[1..10000] of real; num:array[1..10000] of integer; begin readln(n); for i:=1 to n do begin readln(x[i],y[i]); num[i]:=i; end; n0:=1; for i:=1 to n do begin if x[i]<x[n0] then n0:=i; if (x[i]=x[n0]) and (y[i]<y[n0]) then n0:=i; end; for i:=1 to n do if i<>n0 then begin if x[i]=x[n0] then al[i]:=pi/2 else al[i]:=arctan((y[i]-y[n0])/(x[i]-x[n0])) end; for i:=1 to n-1 do {Sorting by angle} for j:=i+1 to n do if (al[j]<al[i]) and (i<>n0) and (j<>n0) then begin b2:=num[i]; num[i]:=num[j]; num[j]:=b2; end; for i:=1 to n div 2 do if i<>n0 then inc(mid) else inc(mid,2); writeln(num[n0],' ',num[mid]); end. Edited by author 05.01.2009 13:11 Edited by author 05.01.2009 13:12 Sorry! I've found a very stupid bug! Now Accepted!!! I think your algo is O(n^2). It's strange, that your have not get TLE... | I need Help | Mihran Hovsepyan {2 kurs of <RAU>} | 1207. Median on the Plane | 30 Dec 2008 21:47 | 1 | I need Help Mihran Hovsepyan {2 kurs of <RAU>} 30 Dec 2008 21:47 Now I can got WA 1,2,3,5,6,7 and TLE14 This is my code wich got WA6 # include <iostream> # include <algorithm> # include <cmath> using namespace std; typedef long double int64; #define sq(x) x*x int64 myx0=2000000001,myy0=2000000001; struct ket { int64 x; int64 y; int hamar; } a[10010]; bool operator <(ket e, ket f) { double de=sqrt(sq(e.x-myx0)+sq(e.y-myy0)); double df=sqrt(sq(f.x-myx0)+sq(f.y-myy0)); return e.x/de>f.x/df; } int main () { int n,i; int ans1,ans2; cin>>n; for(i=0;i<n;i++) { cin>>a[i].x>>a[i].y; a[i].hamar=i+1; if(a[i].y<myy0) { myx0=a[i].x; myy0=a[i].y; ans1=a[i].hamar; } else if(fabs(a[i].y-myy0)<0.00001 && a[i].x<myx0) { myx0=a[i].x; ans1=a[i].hamar; } } swap(a[0],a[ans1-1]); sort(a+1,a+n); ans2=a[n/2].hamar; cout<<ans1<<" "<<ans2; return 0; } Edited by author 30.12.2008 21:48 | who can help me with 7-th test.? thanks | VALERO | 1207. Median on the Plane | 3 Nov 2006 11:10 | 4 | maybe, you can give any tests where my program doesnt work? my algo is : var a : array[0..100001,1..3] of int64; n,i,o,k,l : longint; q,w,e,k1,k2,k3,k4 : int64; s,d : real; procedure sort(l,r: longint); var i,j :longint; x,y,z,w: int64; begin i := l; j := r; x := A[ (l + r) div 2,1 ]; repeat while A[i,1] < x do inc(i); while x < A[j,1] do dec(j); if not (i>j) then begin y := A[i,1]; A[i,1] := A[j,1]; A[j,1] := y; z := A[i,2]; A[i,2] := A[j,2]; A[j,2] := z; w := A[i,3]; A[i,3] := A[j,3]; A[j,3] := w; inc(i); dec(j); end; until i>j; if l < j then sort(l,j); if i < r then sort(i,r); end; procedure vuv; begin if a[k1,3]<a[k2,3] then writeln(a[k1,3],' ',a[k2,3]) else writeln (a[k2,3],' ',a[k1,3]); halt; end; begin read(n); for i:=1 to n do begin read(a[i,1],a[i,2]); a[i,3]:=i; end; if n=2 then begin k1:=1;k2:=2;vuv;end; sort(1,n); k1:=n div 2; d:=0; if a[(n div 2)+1,1]=a[n div 2,1] then k2:=k1+1 else if a[(n div 2)-1,1]<>a[n div 2,1] then begin for i:= 1 to n do if (i<>k1){ and (a[i,1]<>a[k1,1])} then begin s:=abs((a[i,2]-a[k1,2])/(a[i,1]-a[k1,1])); if s>d then begin d:=s;k2:=i;end; end; end else if k1-1>0 then begin k3:=k1-1; k4:=k1; for i:=1 to n do if (i<>k4) and (i<>k3) then begin s:=abs((a[i,2]-a[k3,2])/(a[i,1]-a[k3,1])); if s>d then begin k1:=k3;d:=s;k2:=i;end; s:=abs((a[i,2]-a[k4,2])/(a[i,1]-a[k4,1])); if s>d then begin k1:=k4;d:=s;k2:=i;end; end; end; vuv; end. thanks for all. Edited by author 11.08.2006 14:54 HeapSort is no necessary. Just sort by angle as you do and take (n div 2 + 1) of them Try to use heapsort. When I use qsort -> WA6, heapsort -> AC. | Why WA on test #6? | NIS (liceum 165) | 1207. Median on the Plane | 18 Oct 2006 15:56 | 2 | I am use __int64 and sorting points: inline short polarCmp(int a,int b) { __int64 x1 = __int64(p[a].x)-p[0].x; __int64 y1 = __int64(p[a].y)-p[0].y; __int64 x2 = __int64(p[b].x)-p[a].x; __int64 y2 = __int64(p[b].y)-p[a].y; __int64 vp = x1*y2-x2*y1; return (vp<0)?-1:(vp==0)?0:1; } p[0] - most down left point Edited by author 12.08.2006 13:00 Hm... I'm change QuickSort to Heapsort and get AC!!! | WA on Test#7 Please HELP!!!! | MultiThread | 1207. Median on the Plane | 22 Sep 2006 13:48 | 1 | The code is below: WHY WA :-( #include <stdio.h> struct point { long x; long y; int id; }; void Sort (point points[], int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { double r1 = points[j+1].y * points[j].x; double r2 = points[j].y * points[j+1].x; if (r1 < r2) { point t = points[j]; points[j] = points[j+1]; points[j+1] = t; } } } } void main() { int N = 0; scanf ("%d", &N); const int MAX = 10000; point points[MAX] = {0}; for (int i = 0; i < N; i++) { scanf ("%ld%ld", &points[i].x, &points[i].y); points[i].id = i + 1; } Sort (points, N); printf ("%d %d", points[0].id, points[N/2].id); } | Why WA on Test 7? | Tabledott | 1207. Median on the Plane | 21 Jun 2006 02:01 | 10 | Here is my code: [code deleted] Edited by moderator 23.06.2006 17:17 Use type __int64 in the function "znak":
__int64 znak(point a,point b,point c) { return (__int64)(a.y-b.y)*c.x+(__int64)(b.x-a.x)*c.y+((__int64)a.x*b.y-(__int64)b.x*a.y); } And you'll get AC ;) Yup, you`re right, 10x very much for your help, because me and one of my friends spent so much time in unsuccessful debugging :), anyway I got accepted now, btw keep going the same way in Topcoder High School SRM's :) >> keep going the same way in Topcoder High School SRM's :) :) I would like to keep... But by the rules I'm already not able to participate (I complete school in this year). So yeasterday it was the last one. Well, in this case the battle for the top spot will be more intriguing :) Yup, but if you don't have the opportunity to get good education your chances decrease :) All the knowledge and skills which raised me into the Top of Timus Online Judge have (almost) nothing to do with what the university gave me. I studied everything I need myself :) Well, I've just finished High School so I hope I'll have time to get better :) Btw, it seems at last you solved 1394, I just want to express my admiration to the fact that you didn't gave it up :) Edited by author 21.06.2006 00:47 As for 1394, Vladimir Yakovlev will try to defeat my solution with new tests soon. I think he could succeed. But I also suppose Safe Bird's and N.M.Hieu (DHSP)'s solutions might be beaten as well. | If i'm not wrong In test 4 one of coordinates is +/- 1E9 (-) | Ivankov Dmitry | 1207. Median on the Plane | 4 Oct 2005 03:09 | 2 | You're right! -10^9 <= xi, yi <= 10^9 Problem statement was updated | Help me with my program? | Alexander Bovkun | 1207. Median on the Plane | 3 Apr 2005 01:04 | 2 | Help me to debug my program or give me some tests. Here is my code: [code deleted] Edited by moderator 24.11.2019 23:21 I made a mistake while working with Leftmost point. The part of program wich was not right should look like this: LeftmostIndex:=1; For I:=2 To N Do If P[I].X<P[LeftmostIndex].X Then LeftmostIndex:=I; P[LeftMostIndex].Angle:=-2*Pi; For I:=1 To N Do If I<>LeftMostIndex Then P[I].Angle:=GetAngle(P[LeftmostIndex],P[I]); QSort(1,N); LeftmostIndex is an integer variable. | Why wa on test #7? | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1207. Median on the Plane | 27 Aug 2004 20:45 | 2 | [code deleted] Edited by moderator 24.11.2019 23:22 >> cross:=x1*y2-x2*y1; x1*y2 could exceed the int range! Better do y2/x2-y1/x2 (of course type cast this to double) | Please help, what's wrong with this program | MadPsyentist/Sam | 1207. Median on the Plane | 27 May 2004 21:24 | 8 | i don't really sure if i understand the problem correctly , but his is my program. plase have a look #include <stdio.h> #include <stdlib.h> struct co { double x,y; int id; }; int cmp(const void *a, const void *b) { co p=*((co *)a); co q=*((co *)b); double result=p.x*q.y-p.y*q.x; if (result>0) return 1; else if (result<0) return -1; else return 0; } void main() { const int maxsize=10000; co p[maxsize]; int i,j,k; int size; #ifndef ONLINE_JUDGE freopen("1207.in","r",stdin); freopen("1207.out","w",stdout); #endif scanf("%d",&size); for (i=0; i<size; i++) { scanf("%lf%lf",&(p[i].x),&(p[i].y)); p[i].id=i+1; } qsort(p,size,sizeof(co),cmp); printf("%d %d",p[0].id,p[size/2].id); } > 4 > 1 1 > 2 2 > 1 0 > 2 0 my program output is 3 2 , what's the correct one and why? it seems like I really misunderstand the problem and I don't know what's the point :( Hmm, that's strange. 3 2 is ok, but on my computer it returns 2 4, what is of course wrong. I guess it depends on the realization of qsort. IMHO, your solution is not ok, but I'm not sure. What compiler do you use? quite strange , I use Mingw as compiler, it produces correct answer anyway, my old this solution is wrong as you said > i don't really sure if i understand the problem correctly , but his is my > program. plase have a look > > #include <stdio.h> > #include <stdlib.h> > struct co { > double x,y; > int id; > }; > int cmp(const void *a, const void *b) { > co p=*((co *)a); > co q=*((co *)b); > double result=p.x*q.y-p.y*q.x; > if (result>0) > return 1; > else if (result<0) > return -1; > else > return 0; > } > > void main() { > const int maxsize=10000; > co p[maxsize]; > int i,j,k; > int size; > #ifndef ONLINE_JUDGE > freopen("1207.in","r",stdin); > freopen("1207.out","w",stdout); > #endif > scanf("%d",&size); > for (i=0; i<size; i++) { !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1111 > scanf("%lf%lf",&(p[i].x),&(p[i].y)); !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! (*) > p[i].id=i+1; > } > qsort(p,size,sizeof(co),cmp); > printf("%d %d",p[0].id,p[size/2].id); > } (*) I think the coordinates must be shifted, because the point 0 must be (0, 0) (basis) Edited by author 27.05.2004 21:25 | why lock!!!!!!! | ruwelcome | 1207. Median on the Plane | 7 Jun 2003 18:26 | 1 | | When will the problem unlock? I couldn't solve it | Cloudy | 1207. Median on the Plane | 17 Apr 2003 18:34 | 3 | | When will the problem unlock? | Sum 1 | 1207. Median on the Plane | 18 Feb 2003 19:58 | 1 | | Help,Why WA,thanks! | Bishop | 1207. Median on the Plane | 7 Nov 2002 19:25 | 1 | PROGRAM Ural_1207; TYPE xl=record key:real; code:longint; end; CONST MAXN=1000; VAR a:array[1..MAXN,1..2] of longint; d:array[1..MAXN]of xl; o,i,j,x,y,n:longint; temp:xl; BEGIN assign(input,'T1207.in'); reset(input); readln(n); x:=maxlongint; y:=maxlongint; for i:=1 to n do begin readln(a[i,1],a[i,2]); if (x>a[i,1])or((x=a[i,1])and(y>a[i,2]))then begin x:=a[i,1]; y:=a[i,2]; o:=i; end; end; a[o,1]:=a[n,1]; a[o,2]:=a[n,2]; dec(n); for i:=1 to n do begin dec(a[i,1],x); dec(a[i,2],y); end; for i:=1 to n do begin if a[i,1]<>0 then d[i].key:=a[i,2]/a[i,1] else if a[i,2]<=0 then d[i].key:=-maxlongint else d[i].key:=maxlongint; d[i].code:=i; end; d[o].code:=n+1; for i:=2 to n do for j:=n downto i do if d[j].key<d[j-1].key then begin temp:=d[j]; d[j]:=d[j-1]; d[j-1]:=temp; end; {if x>d[n div 2+1].code then writeln(d[n div 2+1].code,' ',o) else} writeln(o,' ',d[n div 2+1].code); END. | How to do '1205'? | ting | 1207. Median on the Plane | 6 Nov 2002 19:32 | 4 | Please tell me how to do '1205'. Thank you very much. > Please tell me how to do '1205'. > Thank you very much. > There is N + 2 points, n station and A, B. You find the minimum way from A to B. Between 2 point, if they are two station then go by train else go on foot. I hope you will complete it soon. > Please tell me how to do '1205'. > Thank you very much. > The code is as follows: #include <iostream.h> #include <memory.h> #include <iomanip.h> #include <math.h> struct point { double x,y; }; point p[201]; int N; double fv,cv; double graph[202][202]; double dist[202]; int pre[202]; bool s[202]; void main() { cin>>fv>>cv; cin>>N; int i; for (i=1;i<=N;i++) cin>>p[i].x>>p[i].y; int a,b; cin>>a>>b; memset(graph,-1,sizeof(graph)); while ( a>0 && b>0 ) { graph[a][b] = 1; graph[b][a] = 1; cin>>a>>b; } cin>>p[0].x>>p[0].y; cin>>p[N+1].x>>p[N+1].y; int j; for (i=0;i<=N+1;i++) for (j=0;j<=N+1;j++) { if ( i==j ) continue; if ( graph[i][j]==0 ) graph[i][j] = sqrt((p[i].x-p[j].x)*(p [i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y))/fv; else graph[i][j] = sqrt((p[i].x-p[j].x)*(p[i].x- p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y))/cv; } pre[0] = -1; for (i=1;i<=N+1;i++) { dist[i] = graph[i][0]; pre[i] = 0; s[i] = false; } s[0] = true; dist[0] = 0; for (i=0;i<N+1;i++) { double min = 999999; int u = 0; for (j=0;j<=N+1;j++) if ( !s[j] && min>dist[j] ) { u = j; min = dist[j]; } s[u] = true; if ( s[N+1] ) break; for (j=0;j<=N+1;j++) if ( !s[j] && dist[u]+graph[u][j]<dist [j] ) { dist[j] = dist[u]+graph[u][j]; pre[j] = u; } } cout<<setiosflags(ios::fixed)<<setprecision(7)<<dist[N+1] <<endl; int t[202]; int n=0,k = N+1; while ( pre[k]>0 ) { t[n++] = pre[k]; k = pre[k]; } if ( n==0 ) cout<<0<<endl; else { cout<<n<<' '<<t[n-1]; for (i=n-2;i>=0;i--) cout<<' '<<t[i]; cout<<endl; } }
| fuck off | Razenshtein Ilya | 1207. Median on the Plane | 11 Oct 2002 18:01 | 2 | fuck off Razenshtein Ilya 6 Oct 2002 17:17 | Who can help me? | zouyi1 | 1207. Median on the Plane | 10 Aug 2002 17:17 | 3 | if the answer are many,what shall I do? > if the answer are many,what shall I do? sent an e-mail to me. (gdsgzt@163.com) | What's wrong with my answer. Help, please. | meoden | 1207. Median on the Plane | 15 Jun 2002 19:47 | 1 | Here's my source code: {$r+,n+,q+,b-} const maxn=10000; var x,y:array[1..maxn] of longint; a:array[1..maxn] of real; b:array[1..maxn] of integer; n:integer; min,a1,a2:longint; procedure nhap; var i:integer; begin readln(n); min:=maxlongint; for i:=1 to n do begin readln(x[i],y[i]); if (y[i]<min) or ((y[i]=min) and (x[i]>x[a1])) then begin min:=y[i]; a1:=i; end; end; end; procedure shellsort; var i,j,h,tb:integer; ta:real; begin h:=n shr 1; while h<>0 do begin for i:=h+1 to n do begin ta:=a[i]; tb:=b[i]; j:=i-h; while (j>0) and (a[j]>ta) do begin a[j+h]:=a[j]; b[j+h]:=b[j]; j:=j-h; end; a[j+h]:=ta; b[j+h]:=tb; end; h:=h shr 1; end; end; function angle(i,j:integer):real; var dx,dy,ax,ay:longint; t:real; begin dx:=x[j]-x[i]; ax:=abs(dx); dy:=y[j]-y[i]; ay:=abs(dy); if (dx=0) and (dy=0) then t:=0 else t:=dy/(ax+ay); if dx<0 then t:=2-t else if dy<0 then t:=4+t; angle:=t*90; end; procedure init; var i:integer; begin for i:=1 to n do a[i]:=angle(a1,i); for i:=1 to n do b[i]:=i; end; begin nhap; init; shellsort; writeln(a1,' ',b[n div 2+1]); end. |
|
|