Tamflexの貯蔵庫

やる気のない備忘録

aoj 0035

凹みの検知 | Aizu Online Judge

幾何の問題

  • 対角線となる二直線の交差を確認する解法
  • 対角線で三角形2つに分割し面積で求める開放

が等が考えられる. 今回は後者で解いてみた.

でも本当はrubyのコードにあるように
https://www.jaist.ac.jp/~uehara/course/2014/i481f/pdf/ppt-2.pdf
にある辺角の単調増加性を用いてやりたかったけどWAになってしまう...
atan2周りのバグだろうか?

double area(double x1, double y1, double x2, double y2, double x3, double y3)
{
  double a = x2 - x1;
  double b = y2 - y1;
  double c = x3 - x1;
  double d = y3 - y1;
  return fabs(0.5*(a*d-b*c));
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  double x1, y1, x2, y2, x3, y3, x4, y4;
  while(~scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4))
  {
    double a1 = area(x1,y1,x2,y2,x3,y3);
    double a2 = area(x1,y1,x3,y3,x4,y4);
    double a3 = area(x1,y1,x2,y2,x4,y4);
    double a4 = area(x2,y2,x3,y3,x4,y4);
    printf("%s\n",fabs((a1+a2)-(a3+a4))<10e-8?"YES":"NO");
  }
  return 0;
}
require 'scanf'

while line = gets
  s = line.split(',').map(&:to_f)
  q = s.each_slice(2)
  b = q.each_with_index.min_by{|v| v[0][1]}[1]
  a = []
  q = q.map{|v| v}
  n = q.size
  for i in 0..3
    x = q[(i+1)%n][0]-q[i][0]
    y = q[(i+1)%n][1]-q[i][1]
    t = Math.atan2(y,x)
    a.push(t<0 ? t+2*Math::PI : t)
  end
  c = a[b] <= a[(b+1)%n]
  for i in 0..2
    if (a[(b+i)%n] <= a[(b+i+1)%n]) != c
      puts "NO"
      break
    end
    puts "YES" if i == 2
  end
end