四角形に凹があるかについての問題です。

[けん]

問題は次のURLにあります。
http://judge.u-aizu.ac.jp/onlinejudge/d ... sp?id=0035

自分でも考えたのですが、方針が全く立たず、他の人の解答例を参考にしようと思い、一番分かりやすそうなものを選びました。
直線について考えて、それの正負によって答えを出していました。
参考にしたコードは以下のとおりです。

コード:

#include <stdio.h>
 
double mk_func(double x, double x1, double y1, double x2, double y2) {
    return (y1 - y2) / (x1 - x2) * (x - x1) + y1;
}
 
int main() {
    double x1, x2, x3, x4, y1, y2, y3, y4;
 
    while(scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4) != EOF) {
        if((mk_func(x2, x1, y1, x3, y3) - y2) * (mk_func(x4, x1, y1, x3, y3) - y4) > 0)
            printf("NO\n");
        else if((mk_func(x1, x2, y2, x4, y4) - y1) * (mk_func(x3, x2, y2, x4, y4) - y3) > 0)
            printf("NO\n");
 
        else
            printf("YES\n");
    }
 
    return 0;
}
 

今、自分が理解できている部分は
double mk_func(double x, double x1, double y1, double x2, double y2) {
return (y1 - y2) / (x1 - x2) * (x - x1) + y1;
です。
（ｘ１，ｙ１）、（ｘ２，ｙ２）を通る直線を表していると思います。
わからないところは、
if((mk_func(x2, x1, y1, x3, y3) - y2) * (mk_func(x4, x1, y1, x3, y3) - y4) > 0)・・・①
と
if((mk_func(x1, x2, y2, x4, y4) - y1) * (mk_func(x3, x2, y2, x4, y4) - y3) > 0)です。

①については自分で考えてみました。間違っている部分があるかもしれませんが、ご指摘いただけると幸いです。
（ｘ１，ｙ１），（ｘ３，ｙ３）を通る直線の傾きを持っていて、（ｘ２，ｙ１）を通る直線を表していて、それがｙ２よりも大きいか小さいか判別しています。

ここで質問なのですが、
どうして①のようなことをすることによって、四角形の凹がわかるのでしょうか？
長文失礼しました。
よろしくお願いします。

[usao]

えーと，まずその
>他の人の解答例
というのは　正しい回答　なのでしょうか？っていう…（ mk_func()とか余裕で0による除算とかしそうに見えるのですが）

以下，ざっと見での感想ですが，

mk_func()が返すのは，引数で与えられる２点(x1,y1),(x2,y2)を通る直線上での，xに対するyの値　のように見えます．

main()のif　の計算式でやろうとしていることは，おそらくですが
「ある対角線から見て，残りの２頂点が反対側にあるかどうかを調べようとしている」のでしょうが，

・y座標のみで判定している　→　例えば，1番目と3番目の頂点のx座標が等しいデータだったらダメじゃないの？
　（前述の０割になる）
・仮にそういうデータが来なかったのだとしても　対角線は２本あるので　両方しらべるまで"NO"と言えない気がするんだけど
　片側の判定に通っただけで"NO"と答えてしまっている．

というあたりがどうにも間違っているような気がするのですが…

[けん]

ご回答ありがとうございます。

対角線を使って調べるわけですね。

このコードはAOJのサイトに提出すると、OKとでます。

ただ、usaoさんの言うとおり、おかしな点もあると思います。

まだ自分の中では、これがどういう基準を満たしていれば、凹がないといえるのかわかりません・・・

[box]

四角形ABCDにおいて、
点Aと点Cを結ぶ線分（直線ではない）
と
点Bと点Dを結ぶ線分（直線ではない）
とが交点を持つとき、四角形ABCDは凸である
両線分が交点を持たないとき、四角形ABCDは凹である
といえるのではないかと思います。山勘ですけど。

[けん]

boxさん、ご返事ありがとうございます。

なるほど！

線分として考えれば判別出来ますね。

そうなると、あとはどう線分にするかですね。

[けん]

http://dixq.net/forum/viewtopic.php?f=3&t=11504
これとかなり近いと思いました。
外積を使うと、上手くできそうです。

[けん]

できました！
アドバイスありがとうございます！

コード:

#include<stdio.h>
int main(void)
{
	double xa,ya,xb,yb,xc,yc,xd,yd;
	double t1,t2,t3,t4;
	while(scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf",&xa,&ya,&xb,&yb,&xc,&yc,&xd,&yd)!=EOF)
	{
		/*
	a,cを通る直線は(xa-xc)*(y-ya)+(ya-yc)*(xa-x)=0
	b,dを通る直線は(xb-xd)*(y-yb)+(yb-yd)*(xb-x)=0
	*/
	t1=(xa-xc)*(yb-ya)+(ya-yc)*(xa-xb);
	t2=(xa-xc)*(yd-ya)+(ya-yc)*(xa-xd);
	t3=(xb-xd)*(ya-yb)+(yb-yd)*(xb-xa);
	t4=(xb-xd)*(yc-yb)+(yb-yd)*(xb-xc);
	if(t1*t2<0&&t3*t4<0)
	{
		printf("YES\n");
	}
	else
	{
		printf("NO\n");
	}
	}
	
	return 0;
}