ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1332. Genie Bomber

WA on test 13 too :(
Posted by Bhaskara Aditya 4 Jul 2005 07:58
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;
}