题目描述
判断一个点与已知三角形的位置关系。
若点在三角形内（不含边界），输出1；
若点在三角形外（不含边界），输出2；
若点在三角形边界上（不含顶点），输出3；
若点在三角形顶点上，输出4。
样例输入
(0,0)
(3,0)
(0,3)
(1,1)
样例输出
1
思路
O（nm）
模拟，先判断是否在顶点上，再枚举三角形每对点和第四个点的关系，如果为0，就判断是否在两点之间，如果都是在三条边的同一侧，那么就是在三角形内。
var
a,b:string;
x,y,z:
array[
1..
4]
of longint;
i,j,k,l,c:longint;
function pd2(n,m:longint):boolean;
begin
if (y[n]<y[
4])
and(y[
4]<y[m])
then
exit(
true);
exit(
false);
end;
function pd(n,m:longint):boolean;
begin
if (x[n]<x[
4])
and(x[
4]<x[m])
then
if (pd2(n,m))
or(pd2(m,n))
then
exit(
true);
exit(
false);
end;
begin
for i:=
1 to 4 do
begin
readln(a);
k:=pos(
',',a);
b:=
copy(a,
2,k-
2);
val(b,x[i]);
b:=
copy(a,k+
1,length(a)-k-
1);
val(b,y[i]);
end;
for i:=
1 to 3 do
if (x[
4]=x[i])
and(y[
4]=y[i])
then begin writeln(
4);
exit;
end;
for i:=
1 to 3 do
for j:=i+
1 to 3 do
begin
c:=(x[j]-x[i])*(y[
4]-y[i])-(x[
4]-x[i])*(y[j]-y[i]);
if c=
0 then
if (pd(i,j))
or(pd(j,i))
then
begin writeln(
3);
exit;
end;
if c>
0 then z[i]:=
1
else if c<
0 then z[i]:=
2
else begin writeln(
2);
exit;
end;
end;
if (z[
1]=z[
2])
and(z[
2]=z[
3])
then writeln(
1)
else writeln(
2);
end.
转载请注明原文地址: https://ju.6miu.com/read-23931.html
