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

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

A Point in a Triangle(AOJ No.0012)

リポジトリ

A Point in a Triangle(AOJ No.0012)

点P(xp, yp)が点A(x1, y1), B(x2, y2), C(x3, y3)で構成される三角形の内側にある場合はYES, そうでない場合はNOと答える。

アルゴリズム1

 cross(\vec{v}, \vec{w})=|\vec{v}||\vec{w}|sin\theta = v_x w_y - w_x v_y
とする(反時計回りなら正そうでないなら負)。
点Pが△ABCの内側にあるなら
 sign( cross(\vec{AB}, \vec{AP}) ) = sign(cross(\vec{BC}, \vec{BP})) =sign(cross(\vec{CA}, \vec{CP}))
になる。

コード1

javaってComplexクラスないの...?
java.awt.geom.Point2DをimportするとPoint2D.Doubleが使えるが足し算、引き算が無いみたいなので、
それだけでは大して使いやすくはない。
C++で平面幾何を解くとき、std::complexを使うとだいぶ楽に書ける。

import java.awt.geom.Point2D;
import java.util.*;
public class aoj0012 {
	static final Scanner stdin = new Scanner(System.in);
	static double EPS = 1e-10;
	static final Solver solver = Solver.OuterProduct;
	public static void main(String[] args) {
		while( stdin.hasNext() ){
			Point p1 = new Point(stdin.nextDouble(), stdin.nextDouble());
			Point p2 = new Point(stdin.nextDouble(), stdin.nextDouble());
			Point p3 = new Point(stdin.nextDouble(), stdin.nextDouble());
			Point pp = new Point(stdin.nextDouble(), stdin.nextDouble());
			System.out.println( solver.solve(p1, p2, p3, pp) ? "YES" : "NO");
		}
	}
	enum Solver{
		OuterProduct { @Override boolean solve(Point p1, Point p2, Point p3, Point pp){
			Point p12 = p2.sub(p1), p23 = p3.sub(p2), p31 = p1.sub(p3);
			Point p1p = pp.sub(p1), p2p = pp.sub(p2), p3p = pp.sub(p3);
			double s1 = p12.cross(p1p), s2 = p23.cross(p2p), s3 = p31.cross(p3p);
			return ( s1 >= 0 && s2 >= 0 && s3 >= 0 || s1 <= 0 && s2 <= 0 && s3 <= 0 );
		}}, //... abbr. 
		boolean solve(Point p1, Point p2, Point p3, Point pp){ return true; }
	}
	static boolean equal(double a, double b){ return Math.abs(a-b) < EPS; }
	@SuppressWarnings("serial")
	public static class Point extends Point2D.Double {
		public Point(double x, double y){ super(x,y); }
		public final Point sub(Point p){ return new Point( x - p.x, y - p.y ); }
		public final double cross(Point p){ return x * p.y - y * p.x; }
	}
}

アルゴリズム2

点Pが△ABCの内側にあるなら△ABC、△ABP、△BCP、△CAPの面積が
 S_{ABC} = S_{ABP} + S_{BCP} + S_{CAP}\cdots(1)
となるのは自明。
ヘロンの公式(Heron's formula)
 s = \frac{a+b+c}{2}
 S = \sqrt{s(s-a)(s-b)(s-c)}
を使って求めて(1)が成り立つかどうかを調べる。

コード2

static double Heron(Point p1, Point p2, Point p3){
	double a = p1.distance(p2), b = p2.distance(p3), c = p3.distance(p1);
	double s = (a+b+c)/2;
	return Math.sqrt( s*(s-a)*(s-b)*(s-c) );
}
@Override boolean solve(Point p1, Point p2, Point p3, Point pp){
	double S1 = Heron(p1, p2, pp), S2 = Heron(p2, p3, pp), S3 = Heron(p3, p1, pp);
	double SA = Heron(p1, p2, p3);
	return equal(SA, S1+S2+S3);
}