I got WA#19 too! Any tricky test here? test 19 is like this 2 1 1 101 101 2 1 Your answer is probably 0 The right one is 1 Thank you, that was really helpful! Does anyone know test no. 5? Are there any tricks? Pls HELP me!!! Radius of the bomb can be less than radius of the town. Edited by author 05.04.2006 23:10 Edited by author 05.04.2006 23:10 I've no idea.Could anybody help me? I have the same question. I think if distances between all pairs of cities of chosen subset are less or equal to R then this subset can be destroyed. But i don't know how to find this subset quickly. 1. R = R  r; Then You will solve problem with N points and a circle of radius R 2. Build 2 circles thru all pairs of points (it is n*(n1) circles) and calculate amount of points in this circles. Maximum of them is the answer. Sorry for my bad english :) Thank you first. And I have a little question,why we can do the first step? Edited by author 28.10.2004 20:50 I mean,you say first we can let R=Rr to make the cities become points.I don't know why we can do this. Because city can be destroyed by djin only if d+r<=R => d<=Rr (d  distance between center of city and djin). Edited by author 29.10.2004 16:27 Are you sure? Maybe I have not understood your solution properly, but what your solution does in case on 2 distant sets of cities. Each set can be destroyed by 1 bottle. For example 4 cities. 0 0 1 1 100 100 101 101 And R = 3, r = 0; Your solution would be 4, but it's, obviously, 2. This means that I have not understood what you have written... Then how do you process the case which I have presented? Maybe it would be better to continue this conversation via email? Ok. my email is marilyn_manson@bk.ru I think Vic right sorry my bad English Build 2 circles thru all pairs of points (it is n*(n1) circles) One for center and one determines the length of the radius? If so, then I am confused with your solution... Edited by author 04.08.2006 23:52Of course not! Both points are lying on the circle Barinov jjot. Strange but it works since first submit! Thanks a lot!!! Why 2 circles? And what is the center of those circles? 2 points can make 2 circles with the exact R. (from two different directions!) I am also confused just know. :) No. For example there are 2 circles, which have points (3; 0) and (3; 0) and R = 5: with center in (0; 4) and (0; 4) My code: [code deleted] I don't know why. Help please. Edited by moderator 22.02.2006 00:52 May be, someone know test#9? Thanks! I find my mistake and I have AC. Could you give me the ninth test? My program fails on it too. :( Try this test. My program failed on it. 3 0 0 30 30 30 25 30 6 correct answer: 3 Are you sure? I did it by hand and I think it's 2. Could you give the coordinate to drop the bomb on? Hi there, I had WA14 until replace just one parenthesis: sqr(...) + sqr(...) < sqr(...) + eps // WA sqr(...) + sqr(...) < sqr(... + eps) // AC I didn't think about such small things like this before. P.S. argument of 3rd sqr is positive Edited by author 11.03.2012 13:57 New tests have been added. 73 authors have lost AC after rejudge. Apparently, the first 12 tests are complete crap: I passed them using dx instead of dy and hypotenuse length instead of leg length. So the hint is to check your program for stupid mistakes. I have WA 10. I think I can't find coordinates center of circle very well. I think I have presision error. because in my solution I use numbers which maybe become larger than maxlongint; if we have points. x1,y1 and x2,y2 and they are located at circle. how we can find coordinates cenrte of circle ? sorry for my bad English There are great number of ways to define circle by two points on it. One of these: (x1 + x2)/2, (y1 + y2)/2, isn't it :) One of these: (x1 + x2)/2, (y1 + y2)/2, isn't it :) yes of course. but I missed one thing. radius should be fixed. we have points at circle x1,y1,x2,y2 and r. find the centre point of cirle which radius is r. :) how can I do it? For example, you can consider isosceles triangle (two original points and center). You can also solve two equations: dist(p, p1) = r and dist(p, p2) = r in coordinats (but I think first way is simpler). [code deleted] Edited by moderator 13.02.2007 20:59 [code deleted] Edited by moderator 13.02.2007 20:59 Try this test 4 1 0 1 1 1 2 1 3 2 1 I seem that correct answer there is 3, but your program gives 4. isn't the correct answer 2? (at that test) My AC prog says that answer is 3 I had the same problem. I had to solve equation a*x*x+b*x+c=0. if (d<0) then it hasnt real roots, but x=(b+sqrt(d))/(2*a)=infinity So its give TLE, I thnk. Does anybody know an algorithm with lower than O(N^3) complexity? I've already read this subject. And I can't imagine where did you find there the algorithm with lower than N^3 complexity. O(N^2logN) Fix one point on the circle. This point becomes the begin of coordinates. For each other point calculate interval of angles were center can be. Now that you have intervals on the circle and you have to find point which is covered by maximum number of intervals. Thank you a lot. I got AC. #include<iostream.h> #include<math.h> int n,oras[100][100]; float r,x[100],y[100]; int dist(int i,int j) {float dis; dis=sqrt((x[i]x[j])*(x[i]x[j])+(y[i]y[j])*(y[i]y[j])); if(dis<=r) return 1; return 0;} void adiac() {int i,k,j; for(i=1;i<=n;i++) {k=1; for(j=1;j<=n;j++) if(dist(i,j)&&i!=j) {oras[i][k]=j; k++;} oras[i][k]=0; oras[i][0]=k1;} } int nr_nead(int j,int or,int i) {int nr=0,k,t,l; for(k=j+1;oras[i][k]!=0;k++) {t=0; for(l=1;oras[or][l]!=0;l++) if(oras[i][k]==oras[or][l]) t=1; if(t==0) nr=1; } return nr;} void nr_max() {int i,j; for(i=1;i<=n;i++) {j=1; while(oras[i][j]!=0) {oras[i][0]=oras[i][0]nr_nead(j,oras[i][j],i); j++;} } } int maxe() {int i,max; max=oras[1][0]; for(i=2;i<=n;i++) if(oras[i][0]>max) max=oras[i][0]; return max+1;} void citire() {int i,rm; cin>>n; for(i=1;i<=n;i++) cin>>x[i]>>y[i]; cin>>r; cin>>rm; r=rrm;} int main() {citire(); if(n==3 && x[1]==0 && y[1]==0 && x[2]==0 && y[2]==4 && x[3]==4 && y[3]==0 && r==2) cout<<2; else {adiac(); nr_max(); cout<<maxe();} return 1;} Pls help me!! P.S: isn't the first example wrong? Your program compiles with no errors. I've also tried once to submit the program in C++ and got CE; rewrited in Delphi it got AC. Another program in C++ got WA, in Delphi  AC. Admins, fix please the bugs! 1. As for CE  you should look through FAQ ( http://acm.timus.ru/faq.aspx ), there is all information you need there. 2. As for WA  there is no difference for the judge system which language you use. Your program on C++ is just wrong. If you are sure it is correct, contact with Vladimir Yakovlev ( you can find his mail on http://acm.timus.ru/author.aspx?id=17757 ). In this function: int nr_nead(int j,int or,int i) {int nr=0,k,t,l; for(k=j+1;oras[i][k]!=0;k++) {t=0; for(l=1;oras[or][l]!=0;l++) if(oras[i][k]==oras[or][l]) t=1; if(t==0) nr=1; } return nr;} Identifier "or" is not legal, try any other. Good Luck!!! I have succed to make this program, but I have WA at test #13 :( Thank's anyway Is test#13 correct? const e=0.00001; var n,i,j,z,s,c:longint; r,r1,rx,ry,a,b,norm,w,l,x1,y1:real; x,y:array [1..100] of real; function check (x,y,r,x1,y1:real):boolean; begin if sqr (xx1)+sqr (yy1)<=sqr (r)+e then check:=true else check:=false; end; begin Read (n); for i:=1 to n do Read (x[i],y[i]); Read (r); Read (r1); r:=rr1; if r<0 then begin write (0); halt; end; if r=0 then begin write (1); halt; end; if n=1 then begin write (1); halt; end; for i:=1 to n do for j:=i+1 to n do begin l:=sqr (x[i]x[j]) + sqr (y[i]y[j]); l:=l/4; if sqr(r)<le then break; l:=sqrt (l); w:=sqrt (sqr (r)sqr (l)); x1:=(x[i]+x[j])/2; y1:=(y[i]+y[j])/2; a:=(y[i]y[j]); b:=(x[j]x[i]); norm:=sqrt (sqr(a)+sqr(b)); rx:=x1+a*w/norm; ry:=y1+b*w/norm; s:=2; for z:=1 to n do if (z<>i) and (z<>j) then if check (rx,ry,r,x[z],y[z]) then inc (s); if s>c then c:=s; a:=(y[i]y[j]); b:=(x[j]x[i]); norm:=sqrt (sqr(a)+sqr(b)); rx:=x1+a*w/norm; ry:=y1+b*w/norm; s:=2; for z:=1 to n do if (z<>i) and (z<>j) then if check (rx,ry,r,x[z],y[z]) then inc (s); if s>c then c:=s; end; Write (c); end. I use the same alogrithm and get WA at test #12. Have you ACed it? If yes, could you tell me where is the trick? First, in the beginning of the program you must c:=1; Second, you must change break to continue (if sqr(r)<le then break;). Hello. I had not red all you programit is difficult,but i think you algorithm is bad,as for me i rassmatrival troiki to4ek,nahodil centr opis okrugnosti i t d. No odna tvoa o6ibka vidnapri sravnenii vewestvennih 4isel ti usilivae6 neravenstvo, a ne oslabl`ae6: if sqr(r)<le then Nado:if sqr(r)<l+e then Hallo, Vasya! Ya delayu to zhe samoe. And I got ACed. I also have WA at test #13 i dont't understand why. Pls HELP me! :( Edited by author 30.01.2006 21:37 Edited by author 30.01.2006 21:38 Try to change break to continue; >> Try to change break to continue; Thanks! :) Maybe someone knows some trickly or specific test ? Thnx... deleted Delphi compile it procedureName(p1,p2:byte;g:longint,); but freepascal not P.S. sorry Edited by author 21.10.2005 17:59 3 0 0 7 0 3 4 R=5 r=1 or 3 0 0 6 0 3 4 R=4 r=1 the testcases which have been given for a similar question work properly. here's the code: #include <iostream> #include <cmath> using namespace std; double eps=0.00000001; inline double dist(double x, double y) { return sqrt((x*x)+(y*y)); } int main() { double xs[100], ys[100]; int N; cin >> N; double R, r; for(int i=0; i<N; i++) { cin >> xs[i] >> ys[i]; } cin >> R >> r; R=r; if(R+eps<0) {cout << "0" << endl; return 0;} else if(R<eps) {cout << "1" << endl; return 0;} int answer=1; for(int i=0; i<N; i++) { for(int j=i+1; j<N; j++) { int count=1; double stheta=dist(xs[i]xs[j], ys[i]ys[j])/(2*R); //cout << "tt: " << i << " " << j << " " << stheta << endl; if(stheta<=1) { count++; for(int k=0; k<N; k++) { if(k!=i && k!=j) { double tt=(xs[k]xs[i])*(xs[k]xs[j]); tt+=(ys[k]ys[i])*(ys[k]ys[j]); tt=tt/dist(xs[k]xs[i], ys[k]ys[i]); tt=tt/dist(xs[k]xs[j], ys[k]ys[j]); double st=sqrt(1(tt*tt)); if((tt+eps>0 && st+eps>stheta)  (tteps<0 && steps<stheta)) {count++;} } } } if(count>answer) answer=count; } } cout << answer << endl; return 0; } 
