|
|
what a question haha. just read the question carefully What? Sandro don't require to move at all... So I don't understand why use deque while we can solve it with simple max(a, b) I originally read the problem statement as stating that the radius could only be up to 1000 in length. Hence, I was really confused when everyone was saying the problem was really easy. But that nightmare is behind me now. I never figured out how to do it with that kind of restriction of the radius in under 1 second. What would be the optimal algorithm to use for that case? I used the following thing : (1) calculate median_X=sum(X[i] )/n, do the same for Y. (2) Teleport and find max distance from demon to Sandro. The statement describes the precision as 10^-9, but in the second example I see "1.41421356237309" This number has 14 digits behind decimal point. I tried submitting answers with precision 9, 14 and 16. They all WA#1 even though my calculations have to be correct. Does someone know what's the correct precision? Edited by author 14.04.2016 15:20 Edited by author 14.04.2016 15:20 Are you using a high enough precision type? And hopefully don't output anything extra like "result="? Show your code or something. Sandro't have anywhere to teleport him to stay in the point (0;0). Simply calculate the distance of most distant demon! #include<iostream> #include<cmath> #include<iomanip> #include<vector> using namespace std; struct p { double rec1; double rec2; }; int main() { vector<int> v; int n; cin>>n; if(1<=n&&n<=100) { int *ptr=new int[n*2]; for(int i=0;i<(n*2);i++) cin>>ptr[i]; if(n==1) { if(ptr[0]==0) cout<<ptr[0]+1<<" "<<ptr[1]<<" "<<1; else cout<<ptr[0]-1<<" "<<ptr[1]<<" "<<1; system("pause"); return 0; } int lessx=0,highx=0,lessy=1,highy=1; for(int i=2;i<(n*2);i+=2) { if(ptr[i]<ptr[lessx]) lessx=i; if(ptr[i]>ptr[highx]) highx=i; if(ptr[i+1]<ptr[lessy]) lessy=i+1; if(ptr[i+1]>ptr[highy]) {
v.clear(); highy=i+1; v.push_back(i+1); } else if(ptr[i+1]==ptr[highy]) v.push_back(i+1);
}
int point[2]; point[0]=(ptr[lessx]+ptr[highx])/2.0; point[1]=(ptr[lessy]+ptr[highy])/2.0; for(int i=0;i<(n*2);i=i+2) { if(ptr[i]==point[0]) { if(ptr[i+1]==point[1]) { point[1]++;
} } } cout<<point[0]<<" "<<point[1]<<" "; int p1,p2,max,min; if(v.size()>=2) { p1=highy;max=v[0]-1;p2=highy;min=v[0]-1; for(int i=1;i<v.size();i++) { if(ptr[v[i]-1]>point[0]) { if(ptr[v[i]-1]>ptr[max]) p1=v[i]; } else if(ptr[v[i]-1]<ptr[min]) p2=v[i]; } } int highp_y[2]; if(v.size()>=2) { if((ptr[p1-1]-point[0])>(point[0]-ptr[p2-1])) { highp_y[0]=ptr[p1-1]; highp_y[1]=ptr[p1]; } else { highp_y[0]=ptr[p2-1]; highp_y[1]=ptr[p2]; } } else { highp_y[0]=ptr[highy-1]; highp_y[1]=ptr[highy]; } int lessp_x[2]; lessp_x[0]=ptr[lessx]; lessp_x[1]=ptr[lessx+1]; double longr[2]; p s; for(int i=1;i<=2;i++) { if(i==1) { s.rec2=point[0]-lessp_x[0]; if(lessp_x[1]>point[1]) s.rec1=lessp_x[1]-point[1]; else s.rec1=point[1]-lessp_x[1];
longr[0]=sqrt((s.rec1*s.rec1)+(s.rec2*s.rec2));
} else { s.rec1=highp_y[1]-point[1]; if(point[0]==highp_y[0]) { longr[1]=s.rec1; break; } else { if(point[0]>highp_y[0]) s.rec2=point[0]-highp_y[0]; else s.rec2=highp_y[0]-point[0]; longr[1]=sqrt((s.rec1*s.rec1)+(s.rec2*s.rec2)); } } } cout<<fixed<<setprecision(9); if(longr[0]>longr[1]) cout<<longr[0]; else cout<<longr[1];
system("pause"); return 0; } system("pause"); return 0; } It takes me 2 hours. Algo: x,y - the coordinates of a point Sandro. Use random values like this x = 0.666, y = 0.666. Radius of the circle = max distance to the enemy point. Good Luck! Sory for my english. Use print '%.16f' % (result) instead of print result I've got WA on test 4. People who had WA on this test too, what did you fix? I use 2 ternary searchs. Edited by author 29.10.2011 10:37 Edited by author 29.10.2011 10:37 I had WA #4 too. I suppose in that test case the coordinates which my program has given as answer were coincided with some from the input. I got AC as changing them adding some fraction. Yes, that change doesn't guarantees you a correct answer, but if the fraction has about 9 digits after the decimal point the probability of coincidence is negligible. The fraction I used is 0.0111. >I use 2 ternary searchs. Why? Just look for any point, in which isn't placed any monster. If someone have WA#5 check answer precision. The answers of the tests aren't unique. For example for the first sample test my AC program outputs 4.564191068 4.136298156 5.377150309. It can be also 0 0 (and the respective radius). But don't forget to check if the coordinates of your answer don't coincide with some from the input. Even if not - what changes? Yes, I agree - anything ) Yes, he can. And solution of this problem becomes too easy... even funny :) Yes, he can. Sandro can teleport to origin point. Edited by author 02.07.2011 01:25 Edited by author 02.07.2011 01:25 Sandro is AT the origin point :) Yes, it's very easy :) Thanks for idea! In the first sample 7 1 1 1 5 3 6 5 3 8 0 9 5 5 9 Result: 5 4 5 Why not 0 0 sqrt(5^2 + 9^2) or another points? How to determine unique answer? Edited by author 24.09.2011 11:09 Edited by author 24.09.2011 11:10 I don't think there is a unique answer, you can print any of them. Edited by author 09.11.2011 02:04 I calculated points in double. I made all comparings with abs(a-b)<eps; But eps = 10^-9. - AC eps = 10^-8. - AC eps = 10^-7. - AC eps = 10^-6. - AC eps = 10^-5. - AC eps = 10^-4. - AC eps = 10^-3. - AC eps = 10^-2. - AC eps = 10^-1. - AC eps = 10^1. - AC eps = 10^2. - AC eps = 10^3. - AC!!!! eps = 10^4. - WA1. So... I do not know much about contests rules, but it seemes strange for me) RT~~ A simple problem , think carefully~ I don't how to slove this problem.who can help me? What is the test 25? I've already solved the problem, but I want know why my first solution is wrong... Because Sandro can not teleport to the point where a demon is located. #include<iostream> #include<algorithm> #include <list> #include <math.h> #include <iomanip> using namespace std; /*CODE*/ int main() { /*CODE*/ cout<<setprecision(9)<<fixed<</*CODE*/ <<sqrt(r2); return 0; } Using proprietary Intel compiler instead of free and de facto standard GCC is outrageous! I guess ФАС should investigate how this happened :-) I can't understand the problem. Help me,thanks. |
|
|