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
とする(反時計回りなら正そうでないなら負)。
点Pが△ABCの内側にあるなら
になる。
コード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の面積が
となるのは自明。
ヘロンの公式(Heron's formula)
を使って求めて(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); }