UVa 10445 : Make Polygon

問題リンク：http://uva.onlinejudge.org/external/104/10445.html

問題概要：
多角形が与えられる
その多角形の連続する3点からなる角度の最大と最小を求めよ

解法：
全ての角度をみてその中の最大と最小を求める
入力は時計回りで与えられるのか反時計回りで与えられるのかわからないので
あらかじめ任意の方向に固定する
方向の判定は外積を使って多角形の面積を求め、
その面積が正か負かで判定する
正なら反時計回り、負なら時計回りとなる

コード：

#define inf (1<<29)
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

// Library - template - begin

class Point
{
  public:
  double x,y;

  Point(double x = -inf,double y = -inf): x(x),y(y){}

  Point operator + (Point p){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}

};

typedef Point Vector;

double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }

double norm(Point a){ return a.x*a.x+a.y*a.y; }

double abs(Point a){ return sqrt(norm(a)); }

// Library - template - end

// Library - area - begin

double getArea(vector<Point>& vec)
{
  double sum = 0;
  for(int i=0;i<vec.size();i++)
    sum += cross(vec[i],vec[(i+1)%vec.size()]);
  return sum/2.0;
}

// Library - area - end

double getArg(Point A,Point B,Point C)
{
  double a = abs(B-C);
  double b = abs(A-C);
  double c = abs(A-B);
  return acos((b*b+c*c-a*a)/(2.0*b*c));
}

int N;
bool dir;

void compute(const vector<Point> &ps)
{
  double max_angle = 0,min_angle = inf;

  rep(i,N)
    {
      Point a = ps[i];
      Point b = ps[(i+1)%N];
      Point c = ps[(i+2)%N];
      double arg = getArg(b,a,c) * 180.0 / M_PI;
      Vector v1 = b - a;
      Vector v2 = c - a;

      if(cross(v1,v2) < 0)arg = (double)360.0 - arg;

      max_angle = max(max_angle,arg);
      min_angle = min(min_angle,arg);
    }

  printf("%.6f %.6f\n",min_angle,max_angle);
}

int main()
{
  while(cin >> N,N >= 3)
    {
      vector<Point> ps(N);
      rep(i,N)cin >> ps[i].x >> ps[i].y;
      double area = getArea(ps);
      dir = ( ( area > 0 ) ? false : true);
      if(dir)reverse(ps.begin(),ps.end());
      compute(ps);
    }
  return 0;
}