Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Solution | Конобейцев Иван Олегович | 1332. Джинн-бомбардировки | 24 сен 2022 14:39 | 1 |
Solution Конобейцев Иван Олегович 24 сен 2022 14:39 For every pair of points, build circles on them and find their collision points(<= 2). Then for every collision point find number of points on distance < r to it. Maximum is the answer |
What's test#19 ? anything must notice? | tbtbtb | 1332. Джинн-бомбардировки | 4 июн 2019 11:08 | 6 |
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! |
WRONG at test #5 | cublisan | 1332. Джинн-бомбардировки | 26 ноя 2014 21:32 | 3 |
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 |
How to solve this problem? | HybridTheory | 1332. Джинн-бомбардировки | 24 авг 2013 17:48 | 20 |
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*(n-1) 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=R-r 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<=R-r (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 e-mail? Ok. my e-mail is marilyn_manson@bk.ru I think Vic right sorry my bad English Build 2 circles thru all pairs of points (it is n*(n-1) 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) |
WA20, tests or a hint needed | PrankMaN | 1332. Джинн-бомбардировки | 24 авг 2013 17:23 | 1 |
|
To admins: does test1 coincide with the sample test from problem statement? | lenny | 1332. Джинн-бомбардировки | 21 дек 2012 19:12 | 1 |
|
WA on Test 9 | Golovnev Sasha | 1332. Джинн-бомбардировки | 20 июл 2012 03:56 | 6 |
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? |
Funny precision trouble and WA14 | Anatoly | 1332. Джинн-бомбардировки | 11 мар 2012 13:48 | 1 |
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 |
Problem 1332 Genie Bomber. Tests added | Vladimir Yakovlev (USU) | 1332. Джинн-бомбардировки | 1 ноя 2011 17:05 | 1 |
New tests have been added. 73 authors have lost AC after rejudge. |
hint: wa13 | ASK | 1332. Джинн-бомбардировки | 19 окт 2010 03:24 | 1 |
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. |
WA10 help | Giorgi Saghinadze (Tbilisi SU) | 1332. Джинн-бомбардировки | 1 мар 2007 01:43 | 4 |
WA10 help Giorgi Saghinadze (Tbilisi SU) 28 фев 2007 21:57 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). |
W A 13 TEST HELP SOS PLEASE!!!!!! | Виктор Крупко | 1332. Джинн-бомбардировки | 1 фев 2007 23:57 | 6 |
[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 |
why TLE on test 13 ? I use corect N^3 algorithm | Catalin Tiseanu | 1332. Джинн-бомбардировки | 1 фев 2007 23:52 | 2 |
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. |
How solve this problem with N <= 1000? | Matov Dmitry | 1332. Джинн-бомбардировки | 20 июн 2006 13:42 | 7 |
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. |
can anybody tell me why do they give me a compilation error? | cublisan | 1332. Джинн-бомбардировки | 30 янв 2006 22:43 | 5 |
#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]=k-1;} } 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=r-rm;} 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 |
why wa? | Shteiner Sergei | 1332. Джинн-бомбардировки | 30 янв 2006 21:37 | 10 |
why wa? Shteiner Sergei 16 окт 2004 16:05 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 (x-x1)+sqr (y-y1)<=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:=r-r1; 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)<l-e 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)<l-e then break;). Hello. I had not red all you program-it 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 vidna-pri sravnenii vewestvennih 4isel ti usilivae6 neravenstvo, a ne oslabl`ae6: if sqr(r)<l-e 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! :) |
WA #9 | Zerolog1c [LNU] | 1332. Джинн-бомбардировки | 5 дек 2005 21:55 | 1 |
WA #9 Zerolog1c [LNU] 5 дек 2005 21:55 Maybe someone knows some trickly or specific test ? Thnx... |
Compilation error, I not understand WHY. code here | ACM.Anatoliy 'Tolyan_NO' Tolstobroff | 1332. Джинн-бомбардировки | 21 окт 2005 17:53 | 1 |
deleted Delphi compile it procedureName(p1,p2:byte;g:longint,); but freepascal not P.S. sorry Edited by author 21.10.2005 17:59 |
What is the algorithm for this test? | VALERO | 1332. Джинн-бомбардировки | 2 окт 2005 01:05 | 1 |
3 0 0 7 0 3 4 R=5 r=1 or 3 0 0 6 0 3 4 R=4 r=1 |
WA on test 13 too :( | Bhaskara Aditya | 1332. Джинн-бомбардировки | 4 июл 2005 07:58 | 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) || (tt-eps<0 && st-eps<stheta)) {count++;} } } } if(count>answer) answer=count; } } cout << answer << endl; return 0; } |