AOJ_0012 A Point in a Triangle
問題
解法
△ABC = △PAB + △PBC + △+PCA
がなりたてば内部にある。
面積はベクトルの外積を使えば求まるらしい。
#include <cstdio> #include <algorithm> #define EPS 1e-9 class P{ public: double x, y; double cross(P p){ //外積を求める return (x * p.y - y * p.x); } P operator-(const P& p){ P t; t.x = p.x - x; t.y = p.y - y; return t; } }; int main(){ P p[3], v; while(scanf("%lf %lf %lf %lf %lf %lf", &p[0].x,&p[0].y,&p[1].x,&p[1].y,&p[2].x,&p[2].y) != EOF){ scanf("%lf %lf", &v.x, &v.y); double s = abs((p[0] - p[1]).cross(p[0] - p[2])); double t = 0.0; for(int i = 0; i < 3; i++){ double d = abs((v-p[i]).cross(v-p[(i+1)%3])); t += d; //printf("%lf ",d); } //printf("\n%lf %lf\n", s, t); printf("%s\n",(abs(s-t)<EPS)?"YES":"NO"); } }