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

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0068

輪ゴムで囲んだ釘 | Aizu Online Judge
凸包を求めるアルゴリズムが蟻本に乗っていたのでそのまま書いてみた.

class P
{
private:
  double add(double a,double b){if(abs(a+b)<1e-10*(abs(a)+abs(b)))return 0;else return a+b;}
public:
  double x,y;
  P(){};P(double x,double y):x(x),y(y){};
  P operator+(const P&q){return P(add(x,q.x),add(y,q.y));}
  P operator+=(const P&q){x+=q.x;y+=q.y;return *this;}
  P operator-(const P&q){return P(add(x,-q.x),add(y,-q.y));}
  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;}
  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);}
  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);}
  static bool comp(const P&p,const P&q){return (p.x!=q.x)?(p.x<q.x):(p.y<q.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;}
  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));}
};

取り合えず座標をクラス化したのが上のコード.
以下答え.convex_hullが凸包の頂点を返す関数.

vector<P> convex_hull(vector<P> ps)
{
  sort(ps.begin(),ps.end(),P::comp);
  int k = 0, n = ps.size();
  vector<P> qs(n*2);
  for(int i=0;i<n;i++)
  {
    while(k>1&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;
    qs[k++]=ps[i];
  }
  for(int i=n-2,t=k;i>=0;i--)
  {
    while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;
    qs[k++]=ps[i];
  }
  qs.resize(k-1);
  return qs;
}

int main()
{
  int n;
  while(cin >> n, n)
  {
    vector<P> ps,qs;
    REP(i,n){P t;scanf("%lf,%lf\n",&t.x,&t.y);ps.push_back(t);}
    qs = convex_hull(ps);
    cout << n-qs.size() << endl;
  }
  return 0;
}