読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0090

シールの重なり | Aizu Online Judge
二円の交点がどのくらい重なっているか数えれば良い.
ついでに座標を扱うクラスを拡張した.

class P
{
public:
  double x,y;
  P(){};P(double x,double y):x(x),y(y){};
  P operator+(const P&q){P t;t.x=x+q.x;t.y=y+q.y;return t;}
  P operator+=(const P&q){x+=q.x;y+=q.y;return *this;}
  P operator-(const P&q){P t;t.x=x-q.x;t.y=y-q.y;return t;}
  P operator-=(const P&q){x-=q.x;y-=q.y;return *this;}
  template<typename T> P operator*(T d){return P(x*d,y*d);}
  template<typename T> P operator*=(T d){x*=d;y*=d;return *this;}
  template<typename T> P operator/(T d){return P(x/d,y/d);}
  template<typename T> P operator/=(T d){x/=d;y/=d;return *this;}
  bool operator<(const P&q){return (x!=q.x)?(x<q.x):(y<q.y);}
  bool operator>(const P&q){return (x!=q.x)?(x>q.x):(y>q.y);}
  double norm(void){return sqrt(x*x+y*y);}
  double arg(void){return acos(x/this->norm())*P(1,0).sign(*this);}
  P rotate(double t){double c=cos(t),s=sin(t);return P(c*x-s*y,s*x+c*y);}
  P reverseX(void){return P(-x,y);}
  P reverseY(void){return P(x,-y);}
  P unit(void){return (*this).norm()==0?P(0,0):(*this)/(*this).norm();}
  P floor(void){return P((int)x,(int)y);}
  double dot(const P&q){return x*q.x+y*q.y;}
  double det(const P&q){return x*q.y-y*q.x;}
  int sign(const P&q){double d = (*this).det(q); return (d>0)-(d<0);}
  bool on_seg(P p1,P p2,P q){return (p1-q).det(p2-q)==0&&(p1-q).dot(p2-q)<=0;}
  P intersection(P p1,P p2,P q1,P q2){return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));}
};

int main()
{
  int n;
  while(cin >> n,n)
  {
    int m = 1;
    double d;
    vector<P> a(n);
    REP(i,n) scanf("%lf,%lf",&a[i].x,&a[i].y);
    REP(i,n) REP(j,n) if(i!=j&&(d=(a[j]-a[i]).norm())<=2)
    {
      int c1 = 2, c2 = 2; d /= 2;
      P e = (a[j]-a[i]).rotate(M_PI/2).unit();
      P p = (a[i]+a[j])/2+e*sqrt(1-d*d);
      P q = (a[i]+a[j])/2-e*sqrt(1-d*d);
      if(fabs(p.x)<=10&&fabs(p.y)<=10) REP(k,n) if(k!=i&&k!=j&&(p-a[k]).norm()<=1) c1++;
      if(fabs(q.x)<=10&&fabs(q.y)<=10) REP(k,n) if(k!=i&&k!=j&&(q-a[k]).norm()<=1) c2++;
      m = max(m,max(c1,c2));
    }
    cout << m << endl;
  }
}