Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Why I always WA on text 2? | beststu | 1173. Lazy Snail | 18 ноя 2015 20:24 | 3 | Why I always WA on text 2? If you sort points by angle from Wally's home, there is one tricky case - when angle difference between two sequential points is greater than PI. For example if angle range is [-PI; PI]: 0 0 3 -1 -1 1 0 1 2 -1 1 3 Program that sort angles will output 0 1 2 3 0 and it is wrong, 1-2 will intersect with 3-0. Text for angle range [0; 2PI] is 0 0 3 1 1 1 0 -1 2 1 -1 3 Again sorting program will output 0 1 2 3 0 and again it is wrong, 1-2 will intersect with 3-0. Hint: after sorting there may be not more than one pair of sequential points with angle difference greater than PI. | Your first test is not sample. ( | -XraY- | 1173. Lazy Snail | 22 апр 2013 14:49 | 2 | | Problem 1173 "Lazy Snail" has been rejudged | Sandro (USU) | 1173. Lazy Snail | 22 апр 2013 02:11 | 1 | New tests were added. 123 authors lost AC after rejudge. | Can anyone tell me how to solve this problem? | Marko Tintor (marko@pkj.co.yu) | 1173. Lazy Snail | 27 ноя 2010 23:58 | 2 | | why I got WA? | qwt | 1173. Lazy Snail | 27 ноя 2010 23:57 | 3 | var a:array[0..1000,1..3] of real; x,y,x0,y0:real; n,i,j,k:integer; begin readln(x0,y0); readln(n); fillchar(a,sizeof(A),0); for i:=1 to n do begin readln(x,y,a[i,3]); x:=x-x0;y:=y-y0; a[i,1]:=x;a[i,2]:=y; end; for i:=1 to n-1 do for j:=i+1 to n do if a[i,1]*a[j,2]-a[i,2]*a[j,1] >0 then begin a[0]:=a[i];a[i]:=a[j];a[j]:=a[0]; end; writeln(0); for i:=1 to n do begin writeln(a[i,3]:0:0); end; writeln(0); end. Edited by author 27.11.2010 23:57 Edited by author 27.11.2010 23:58 | It doesn'e need convexhull. Sorting is enough! | shrek | 1173. Lazy Snail | 27 ноя 2010 23:56 | 4 | Yeah... Came back to this problem when realized that myself :) I had solved problem by building O(N) convex hulls and then unifying them up from the deepest. How to solve it with only sort? Give me some hints please how to use convexhull in O(n), when the input have arbitary order, "skorKNURE" or any person plz help and explain this algo to me? sorry for my poor englis. GOOD LUCK!!! | † ADMINS † | Anatoliy 'Tolyan_NO' Tolstobroff | 1173. Lazy Snail | 27 авг 2005 03:08 | 5 | † ADMINS † Anatoliy 'Tolyan_NO' Tolstobroff 25 авг 2005 02:42 On the 1st line of input, there will be 2 real numbers: X and Y, separated by a blank, representing the coordinates of Wally's house. On the 2nd line, there will be an integer number: N (2 <= N <= 1000), my program var x,y,n:longint; begin readln(x,y); readln(n); while n=0 do begin end; end. Why i got TLE test1????? N=2...1000 test 1 correct???? var x,y:real; n:longint; begin readln(x,y); readln(n); while n=0 do begin end; end again thank. Tolstobrov_Anatoliy[Ivanovo SPU] 27 авг 2005 03:08 I got AC. Vladimir Yakovlev (USU) i never foget what you do for me. I you friend for all my life. | It seems to me that either test incorrect or checker is invalid | Krayev Alexey(PSU-Again) | 1173. Lazy Snail | 11 авг 2005 19:26 | 1 | First i build convex hull, then for the rest of points i choose the nearest point to convex hull and include it in hull. But i get wa#2 all the time. So I suppose that either tests incorrect (for example 3 points share the same line) or checker is incorrect. Maybe of course i made mistake but i spent a day finding it and nothing. People, help me please!!!!!! #include <list> #include <math.h> using namespace std; #define sqr(x) ((x)*(x)) typedef list<int> ilist; typedef ilist::iterator ilit; #define eps 1e-8 struct tp{ double x, y; int id; }; //int cnt; tp pt[1003]; int npt, n, cnt1; int comp[1003]; double tdist[1003]; ilit to[1003]; ilist reshull; int fres; double getlen(tp &p1, tp &p2){//checked return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y)); } int above(tp &p1, tp &p2, tp &what){//checked double temp; temp=((p2.x-p1.x)*(what.y-p1.y)-(p2.y-p1.y)*(what.x-p1.x)); if (temp>eps) return 1; else if (temp<-eps) return -1; else return 0; } double getdist(tp &p1, tp &p2, tp &what){//checked return fabs((p2.x-p1.x)*(what.y-p1.y)-(p2.y-p1.y)*(what.x-p1.x))/getlen(p1, p2); } void quickhull(tp &start, tp &fin, ilit forins){//checked int oldcnt=cnt1; int i, maxi; double maxdist=-1, dist; bool is=false; ilit newp; for (i=1; i<=n+1; i++) if (comp[i]==oldcnt){ is=true; dist=getdist(start, fin, pt[i]); if (dist>maxdist){ maxdist=dist; maxi=i; } } if (!is) return ; newp=forins; newp++; newp=reshull.insert(newp, maxi); cnt1++; for (i=1; i<=n+1; i++) if (comp[i]==oldcnt && i!=maxi){ fres=above(start, pt[maxi], pt[i]); if (fres==1) comp[i]=cnt1; else if (fres==0) while (true) i=i; } quickhull(start, pt[maxi], forins); cnt1++; for (i=1; i<=n+1; i++) if (comp[i]==oldcnt && i!=maxi){ fres=above(pt[maxi], fin, pt[i]); if (fres==1) comp[i]=cnt1; else if (fres==0) while (true) i=i; } quickhull(pt[maxi], fin, newp); } double getdist1(tp &p1, tp &p2, tp &what){//checked double w1, w2; w1=(p2.x-p1.x)*(what.x-p1.x)+(p2.y-p1.y)*(what.y-p1.y); w2=(what.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(what.y-p2.y); if (w1>eps && w2>eps) return getdist(p1, p2, what); else if (w1<eps) return getlen(p1, what); else return getlen(p2, what); } int main(){//checked #ifndef ONLINE_JUDGE freopen("i.txt","r", stdin); freopen("o.txt", "w", stdout); #endif scanf("%lf %lf", &pt[1].x, &pt[1].y); pt[1].id=0; // npt=1; scanf("%d", &n); int i; // if (n>20) while (true) i=i;
for (i=2; i<=n+1; i++){ scanf("%lf%lf%d", &pt[i].x, &pt[i].y, &pt[i].id); } int maxx, minx; maxx=minx=1; for (i=2; i<=n+1; i++){ if (pt[minx].x>pt[i].x) minx=i; if (pt[maxx].x<pt[i].x) maxx=i; } reshull.push_front(minx); reshull.push_back(maxx); //p2=reshull.begin(); p2++; cnt1++; for (i=1; i<=n+1; i++) if (i!=minx && i!=maxx){ fres=above(pt[minx], pt[maxx], pt[i]); if (fres==1) comp[i]=cnt1; else if (fres==0) while (true) i=i; } ilit p1, p2, p3; p2=p1=reshull.begin(); p2++; quickhull(pt[minx], pt[maxx], p1); cnt1++; for (i=1; i<=n+1; i++) if (i!=minx && i!=maxx){ if (above(pt[minx], pt[maxx], pt[i])==-1) comp[i]=cnt1; } quickhull(pt[maxx], pt[minx], p2); int inhull=0; for (p1=reshull.begin(); p1!=reshull.end(); p1++){ i=pt[*p1].id; tdist[*p1]=-1; inhull++; } double tempdist, tempdist1; reshull.push_back(minx); for (i=1; i<=n+1; i++) if (tdist[i]!=-1){ tdist[i]=100000000l; for (p2=p1=reshull.begin(), p1++; p1!=reshull.end(); p1++, p2++){ tempdist=getdist1(pt[*p2], pt[*p1], pt[i]); if (tdist[i]>tempdist){ tdist[i]=tempdist; to[i]=p2; } }
} int j; int mini; for (j=1; j<=n+1-inhull; j++){ mini=-1; for (i=1; i<=n+1; i++) if (tdist[i]!=-1 && (mini==-1 || tdist[i]<tdist[mini])) mini=i; tdist[mini]=-1; p3=p1=to[mini]; i=*p3; i=*(p3++); p2=reshull.insert(p3, mini); for (i=1; i<=n+1; i++) if (tdist[i]!=-1){ tempdist=getdist1(pt[*p1], pt[*p2], pt[i]); tempdist1=getdist1(pt[*p2], pt[*p3], pt[i]); if (tdist[i]>tempdist-eps){ tdist[i]=tempdist; to[i]=p1; } if (tdist[i]>tempdist1-eps){ tdist[i]=tempdist1; to[i]=p2; }
} } if (pt[*(p1=reshull.begin())].id==0){ for (; p1!=reshull.end(); p1++) printf("%d\n", pt[*p1].id); return 0;
} for (p1=reshull.begin(); pt[i=(*p1)].id!=0; p1++) i=i; printf("0\n"); for (p1++; p1!=reshull.end(); p1++) printf("%d\n", pt[i=*p1].id); p1=reshull.begin(); p1++; for (; pt[*p1].id!=0; p1++) printf("%d\n", pt[i=*p1].id); printf("0\n");
return 0; } Edited by author 11.08.2005 19:32 | There is one more idea can bring AC. My program build convex hull (-) | Kit | 1173. Lazy Snail | 13 июл 2005 21:02 | 1 | | How to solve this problem? it seems very difficult!!! | Colin | 1173. Lazy Snail | 25 окт 2004 15:50 | 3 | It's quite simple , just a sorting problem if u want more detail , mail me at sephiroth_vn@yahoo.com ;) | I think this is a good problem.My algorithm is O(nlogn). | Yu YuanMing | 1173. Lazy Snail | 3 июл 2004 18:09 | 1 | | why i got WA ? who can help me? | ruwelcome | 1173. Lazy Snail | 29 апр 2003 12:21 | 1 | var i,j,k,n,m,s:longint; xx:real; x,y:array[0..1000] of real; a:Array[0..1000] of integer; an:array[0..1000] of real; d:array[0..1000] of integer; begin readln(x[0],y[0]); readln(n); for i:=1 to n do readln(x[i],y[i],d[i]); for i:=1 to n do begin x[i]:=x[i]-x[0]; y[i]:=y[i]-y[0]; end; for i:=1 to n do for j:=i+1 to n do if ((x[i]=x[j]) and (y[i]=y[j])) or ((x[i]=0) and (y[i]=0))then begin writeln(-1); halt; end; writeln(0); fillchar(a,sizeof(a),0); fillchar(an,sizeof(an),0); s:=0; for i:=1 to n do if (x[i]=0) and (y[i]>0) then writeln(i); for i:=1 to n do if (x[i]>0) and (y[i]>=0) then begin inc(s); a[s]:=i; an[s]:=arctan(y[i]/x[i]); end; for i:=1 to s-1 do for j:=1 to s-i do if an[j]<an[j+1] then begin k:=a[j]; a[j]:=a[j+1]; a[j+1]:=k; xx:=an[j]; an[j]:=an[j+1]; an[j+1]:=xx; end; for i:=1 to s do writeln(d[a[i]]); fillchar(a,sizeof(a),0); fillchar(an,sizeof(an),0); s:=0; for i:=1 to n do if (x[i]>0) and (y[i]<0) then begin inc(s); a[s]:=i; an[s]:=arctan(-1*y[i]/x[i]); end; for i:=1 to s-1 do for j:=1 to s-i do if an[j]>an[j+1] then begin k:=a[j]; a[j]:=a[j+1]; a[j+1]:=k; xx:=an[j]; an[j]:=an[j+1]; an[j+1]:=xx; end; for i:=1 to s do writeln(d[a[i]]); for i:=1 to n do if (x[i]=0) and (y[i]<0) then writeln(i); fillchar(a,sizeof(a),0); fillchar(an,sizeof(an),0); s:=0; for i:=1 to n do if (x[i]<0) and (y[i]<=0) then begin inc(s); a[s]:=i; an[s]:=arctan(y[i]/x[i]); end; for i:=1 to s-1 do for j:=1 to s-i do if an[j]<an[j+1] then begin k:=a[j]; a[j]:=a[j+1]; a[j+1]:=k; xx:=an[j]; an[j]:=an[j+1]; an[j+1]:=xx; end; for i:=1 to s do writeln(d[a[i]]); fillchar(a,sizeof(a),0); fillchar(an,sizeof(an),0); s:=0; for i:=1 to n do if (x[i]<0) and (y[i]>0) then begin inc(s); a[s]:=i; an[s]:=arctan(-1*y[i]/x[i]); end; for i:=1 to s-1 do for j:=1 to s-i do if an[j]>an[j+1] then begin k:=a[j]; a[j]:=a[j+1]; a[j+1]:=k; xx:=an[j]; an[j]:=an[j+1]; an[j+1]:=xx; end; for i:=1 to s do writeln(d[a[i]]); writeln(0); end. | Whats wrong with my algorithm or code? | Locomotive | 1173. Lazy Snail | 14 фев 2003 00:22 | 5 | First i calculate the degree between wally house and every friend by procedure ATG and then sort friends by their degree... Type Point =record x,y,d :real; ID :Integer; end; Var a :array[0..1000] of point; n,i :integer; function partition(first,last:integer):integer; Var t :point; i,j :integer; x :real; begin i:=first-1; j:=last+1; x:=a[first].d; while true do begin repeat inc(i); until a[i].d<=x; repeat dec(j); until a[j].d>=x; if i<j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end else begin partition:=j; exit; end; end; end; Procedure qsort(first,last:integer); Var w :integer; begin if first<last then begin w:=partition(first,last); qsort(first,w); qsort(w+1,last); end; end; Function ATG(x:integer):real; Var dx,dy,k :real; begin dx:=a[x].x-a[0].x; dy:=a[x].y-a[0].y; if dx=0 then k:=90 else k:=arctan(dy/dx)/pi*180; if (k<0) or ((k=0) and (dx<0)) then k:=k+180; if dy<0 then k:=k+180; atg:=k; end; begin readln(a[0].x,a[0].y); readln(n); for i:=1 to n do begin readln(a[i].x,a[i].y,a[i].ID); a[i].d:=ATG(i); end; qsort(1,n); writeln(0); for i:=1 to n do writeln(a[i].Id); writeln(0); end. > First i calculate the degree between wally house and every friend by > procedure ATG and then sort friends by their degree... > > Type > Point =record > x,y,d :real; > ID :Integer; > end; > Var > a :array[0..1000] of point; > n,i :integer; > > function partition(first,last:integer):integer; > Var > t :point; > i,j :integer; > x :real; > begin > i:=first-1; > j:=last+1; > x:=a[first].d; > while true do > begin > repeat inc(i); > until a[i].d<=x; > repeat dec(j); > until a[j].d>=x; > if i<j then begin > t:=a[i]; a[i]:=a[j]; a[j]:=t; end > else begin > partition:=j; exit; end; > end; > end; > > Procedure qsort(first,last:integer); > Var > w :integer; > begin > if first<last then > begin > w:=partition(first,last); > qsort(first,w); > qsort(w+1,last); > end; > end; > > Function ATG(x:integer):real; > Var > dx,dy,k :real; > begin > dx:=a[x].x-a[0].x; > dy:=a[x].y-a[0].y; > if dx=0 then > k:=90 > else > k:=arctan(dy/dx)/pi*180; > if (k<0) or ((k=0) and (dx<0)) then k:=k+180; > if dy<0 then k:=k+180; > atg:=k; > end; > > begin > readln(a[0].x,a[0].y); > readln(n); > for i:=1 to n do > begin > readln(a[i].x,a[i].y,a[i].ID); > a[i].d:=ATG(i); > end; > qsort(1,n); > writeln(0); > for i:=1 to n do > writeln(a[i].Id); > writeln(0); > end. > may you tell me a test???? See(+) Miguel Angel 12 фев 2003 01:40 Think of the following Input: 0 0 3 1 0 1 0 -1 2 1 -1 3 Output: 0 2 3 1 0 Luck! at last i correct my solution here: if there where two friend with house number i and i+1 which a[i+1]-a[i]>180 (it is obvious that there will be at last just one of this type) then path be i+1-i+2-...-n-...-1-2-3-...-i Thanks a lit for another AC :) yours Aidin_n7@hotmail.com | At Last i found my error anyone want to change his slon with mine my idea is here: | Locomotive | 1173. Lazy Snail | 14 фев 2003 00:19 | 1 | Hi I calculate every friend`s degree to wally house and then sort them and with a little bit change write them... but i know there is another way to swap endpoint of line if two line cut eachother such as * * * * ** ** * * * * Gets * * * * * * * * * * * * anyonw want to change his solutin with mine? Aidin_n7@hotmail.com | What's wrong with my program?Please help me! | xzl | 1173. Lazy Snail | 15 мар 2002 11:32 | 2 | const limit =1000; type Tnode =record id :integer; dig :extended; end; var s :array[1..limit] of Tnode; n :integer; procedure init; var x,y,bx,by :extended; i :integer; begin read(bx,by,n); for i:=1 to n do with s[i] do begin read(x,y,id); x:=x-bx;y:=y-by;dig:=abs(y)/sqrt(x*x+y*y); if y>0 then if x>0 then dig:=1-dig else dig:=3+dig else if x>0 then dig:=1+dig else dig:=3-dig end; end; procedure sift(p,tot:integer); var i,q :integer; d :extended; begin i:=s[p].id;d:=s[p].dig; while true do begin q:=p+p; if (q<tot) and (s[q].dig<s[q+1].dig) then inc(q); if (q>tot) or (s[q].dig<d) then begin s[p].id:=i;s[p].dig:=d;exit; end; s[p]:=s[q];p:=q; end; end; procedure work; var temp :Tnode; i :integer; begin for i:=n div 2 downto 1 do sift(i,n); for i:=n downto 1 do begin temp:=s[i]; s[i]:=s[1]; s[1]:=temp; sift(1,i-1); end; end; procedure out; var i :integer; begin writeln(0); for i:=1 to n do writeln(s[i].id); writeln(0); end; BEGIN init; work; out; END. what about this case: 0 0 3 5 1 1 4 2 2 -8 1 3 | Why I get WA? Pelase, help me!!!!!!! | Happy New Year! Russia. | 1173. Lazy Snail | 15 мар 2002 11:26 | 6 | My program: Program t1173;{$N+} Const Eps=1E-20; Var Snail :array[0..1000]of record X,Y,W :extended; ID :longint; Use:boolean end; PredW,MinW :extended; i,N,CurI,j :longint; Function GetW(CurX,CurY:extended):extended; Var CurW,tgW,absW :extended; begin if Abs(CurX)<Eps then begin if CurY>0 then CurW:=90; if CurY<=0 then CurW:=270; end else if Abs(CurY)<Eps then begin if CurX>0 then CurW:=0; if CurX<=0 then CurW:=180; end else begin tgW:=abs(CurY/CurX); absW:=ArcTan(tgW)*360/(2*Pi); if (CurX>0)and(CurY>0) then CurW:=absW else if (CurX>0)and(CurY<0) then CurW:=360-absW else if (CurX<0)and(CurY>0) then CurW:=180-absW else if (CurX<0)and(CurY<0) then CurW:=180+absW; end; GetW:=CurW; end; begin Snail[0].ID:=0; Read(Snail[0].X,Snail[0].Y); Read(N); for i:=1 to N do Read(Snail[i].X,Snail[i].Y,Snail[i].ID); for i:=1 to N do Snail[i].W:=GetW(Snail[i].X-Snail[0].X,Snail[i].Y- Snail[0].Y); for i:=1 to N do Snail[i].Use:=false; PredW:=361; Writeln(0); for j:=1 to N do begin MinW:=-1; CurI:=0; for i:=1 to N do if not(Snail[i].Use) then if (Snail[i].W>MinW)and(PredW>Snail[i].W) then begin MinW:=Snail[i].W; CurI:=i; end; PredW:=MinW; Snail[CurI].Use:=true; Writeln(Snail[CurI].ID); end; Writeln(0); end. there might be some problems with tests like this: 0 0 3 2 0 1 1 1 2 1 -1 3 I think you've caught the idea - we don't know which range should we choose - from 0 to 2*pi or from -pi to pi or smth... But this bug can be easily removed. If you still need a hint, email me. Could you explain with more detailed what's wrong with the test case you print?? Thanks for all :) If you draw picture for my answer you'll see what's wrong: * | | *----|--* \ | \ | \ | \| * what about this case 0 0 3 -1 -8 1 -2 -7 2 8 1 3 | Why do I get WA? | Alexandru Mosoi | 1173. Lazy Snail | 25 янв 2002 18:10 | 3 | This is my program. #include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct { long int x, y; int u, id; } snail; snail s[1001]; int d[1002]; int n, k; int cmp_snail(const void *a, const void *b) { snail *c = (snail *)a; snail *d = (snail *)b;
if(c -> x == d -> x) return c -> y - d -> y; return c -> x - d -> x; } int main(void) { int i;
memset(s, 0, sizeof(s)); scanf("%ld%ld", &s[0] . x, &s[0] . y); s[0] . id = 0; scanf("%d", &n);
for(i = 1; i <= n; i ++) scanf("%ld%ld%d", &s[i] . x, &s[i] . y, &s[i] . id);
qsort(s, n + 1, sizeof(snail), cmp_snail);
d[0] = 0; k = 1; s[0] . u = 1;
for(i = 1; i <= n; i ++) { int find = 1; d[k ++] = i; while(find && k > 2) { long int x1 = s[d[k - 3]] . x; long int y1 = s[d[k - 3]] . y; long int x2 = s[d[k - 2]] . x; long int y2 = s[d[k - 2]] . y; long int x = s[d[k - 1]] . x; long int y = s[d[k - 1]] . y; long int a = y1 - y2; long int b = x2 - x1; long int c = y2 * x1 - y1 * x2; long int v = a * x + b * y + c;
if(v > 0) { d[k - 2] = d[k - 1]; k --; } else if(v == 0) { printf("-1\n"); return 0; } else find = 0; } } printf("k = %d; %d\n", k, s[0] . id);
for(i = 0; i < k; i ++) s[d[i]] . u = 1;
for(i = n; i >= 0; i --) if(!s[i] . u) d[k ++] = i;
k = -1; for(i = 0; i <= n && k == -1; i ++) if(s[d[i]] . id == 0) k = i;
for(i = 0; i <= n; i ++) { printf("%d\n", s[d[k]] . id); k ++; k %= n + 1; } printf("0\n"); } I tested it using many random tests. I tested it usign GRX from djgpp and all seemed OK. Why do I get WA? for(i = 0; i <= n; i ++) { printf("%d\n", s[d[k]] . id); /** k ++; k %= n + 1; **/ k = (k+1)%(n+1); } printf("0\n"); I don't check very well your program, but at first glance it's look ok, but a detail. I argumented your program, you'll see isn't the same. Good Luck. > for(i = 0; i <= n; i ++) > { > printf("%d\n", s[d[k]] . id); > /** k ++; > k %= n + 1; **/ > k = (k+1)%(n+1); > } > printf("0\n"); > > > I don't check very well your program, but at first glance it's look > ok, but a detail. I argumented your program, you'll see isn't the > same. Good Luck. No, it didn't work. But thanks for thinking about. |
|
|