平面上に(x1,y1)(x2,y2)(x3,y3)を頂点とした三角形と点P(xp,yp)があります。点Pが三角形の内側にあるときはYES、外側にあるときはNOを出力するプログラムを作成する。なお、点Pはは三角形の頂点や辺の上にはないものとし、与えられる数字は-100以上100以下とする。
x1(実数)
y1(実数)
x2(実数)
y2(実数)
x3(実数)
y3(実数)
xp(実数)
yp(実数)
YES または NO
0.0
0.0
2.0
0.0
2.0
2.0
1.5
0.5
YES
すごく簡単な方法があります。
指定された点からどこでも良いのでまっすぐに線を延ばしていきます。すると何個か交点が出来ると思います。数えておいてください。そして、その数が奇数であれば内側になります。
今回はとりあえず、上下(y軸に平行)に延ばしてみようと思います。また、頂点上は一回しか処理を行わないように注意しましょう。
今回はまず下へ延ばし、今度は上に延ばします。コレは、たとえば「0 1 3 0 2 3 0 2」のようなデータに対応するためです。
ベクトルを使う方法もあるそうです。
#include <stdio.h> //1の点上は含む、2の点上は含まない。 int kousaHantei_shita(double x1,double y1,double x2,double y2,double xp,double yp) { //y軸に平行な線を引く。x1とx2が等しければ、問題条件より交点はない。 if(x1 != x2){ //x1 <= xp < x2 又は x2 < xp <= x1の範囲でなければ交差せず。 if((x1 <= xp && xp < x2 ) || (x2 < xp && xp <= x1)){ //直線の式を求める。y = a*x +b double a = (y2-y1)/(x2-x1); double b = y1 - a * x1; double kouy = a * xp +b; //下方向へ if(kouy < yp){ return 1; } } } return 0; } //1の点上は含む、2の点上は含まない。 int kousaHantei_ue(double x1,double y1,double x2,double y2,double xp,double yp) { //y軸に平行な線を引く。x1とx2が等しければ、問題条件より交点はない。 if(x1 != x2){ //x1 <= xp < x2 又は x2 < xp <= x1の範囲でなければ交差せず。 if((x1 <= xp && xp < x2 ) || (x2 < xp && xp <= x1)){ //直線の式を求める。y = a*x +b double a = (y2-y1)/(x2-x1); double b = y1 - a * x1; double kouy = a * xp +b; //上方向へ if(kouy > yp){ return 1; } } } return 0; } int main(){ double x1,y1,x2,y2,x3,y3,xp,yp; int kousa; scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&x1,&y1,&x2,&y2,&x3,&y3,&xp,&yp); kousa =0; kousa += kousaHantei_shita(x1,y1,x2,y2,xp,yp); kousa += kousaHantei_shita(x2,y2,x3,y3,xp,yp); kousa += kousaHantei_shita(x3,y3,x1,y1,xp,yp); if(kousa & 1){ kousa =0; kousa += kousaHantei_ue(x1,y1,x2,y2,xp,yp); kousa += kousaHantei_ue(x2,y2,x3,y3,xp,yp); kousa += kousaHantei_ue(x3,y3,x1,y1,xp,yp); if(kousa & 1){ printf("YES\n"); return 0; } } printf("NO\n"); return 0; }
結構迷いましたし、実装もあんまりエレガントではありませんが、まあ、良いとします。意味が分からなければ掲示板で聞いてください。