[Atelier Blue アトリエブルー]Homeコンテストパソコン甲子園2003年本選>15問目

15問目(内外判定)

問題

平面上に(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」のようなデータに対応するためです。

ベクトルを使う方法もあるそうです。

ソースコード

お持ち帰り

C/C++

#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;
}


その他

結構迷いましたし、実装もあんまりエレガントではありませんが、まあ、良いとします。意味が分からなければ掲示板で聞いてください。


ページの一番上へ
前のページへ 一覧に戻る 次のページへ
初版2006-5-14 最終更新2006-7-12
[Atelier Blue アトリエブルー]Homeコンテストパソコン甲子園2003年本選>15問目