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

Does anyone know test no. 5? Are there any tricks?
Pls HELP me!!!

I've no idea.Could anybody help me?

3
0 0
0 4
4 0
3 1

My code:

[code deleted]

I don't know why. Help please.

Edited by moderator 22.02.2006 00:52

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

[code deleted]

Edited by moderator 13.02.2007 20:59

Does anybody know an algorithm with lower than O(N^3) complexity?

#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?

Is test#13 correct?

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) || (tt-eps<0 && st-eps<stheta)) {count++;}
               }
            }
         }
         if(count>answer) answer=count;
      }
   }
   cout << answer << endl;
   return 0;
}