围困
Time Limit: 1000 MS Memory Limit: 65536 K
Total Submit: 360(138 users) Total Accepted: 157(129 users) Rating: Special Judge: No
Description
Leyni是一名猎人，一天他在草原中散步，遇到了三只老狼，三只老狼围成了一个三角形，如果Leyni在这个三角形中，那么他必死无疑，否则他还有一线生机。
现在已知三只老狼的坐标和Leyni的坐标，请问，Leyni还有活下去的机会吗？
Input
本题有多组测试数据，对于每组测试数据：
第一行，含有4对坐标，x1, y1, x2, y2, x3, y3, xLeyni, yLeyni。前3对坐标表示三只老狼的位置，最后一对表示Leyni的坐标。坐标的范围在[-10000, 10000]，且都是整数。
注：输入数据保证Leyni不会在三角形的边上。
Output
对于每组测试数据：
第一行，如果Leyni还有一线生机，那么请输出Live，否则请输出Die
Sample Input
-1 -1 1 -1 0 1 0 0
-1 -1 1 -1 0 1 10 10
Sample Output
Die
Live
Author
齐达拉图
计算几何，基础题，判断点是否在三角形内。
这道题可以用来练习叉积的应用，思路是如果Leyni位置的点与三个顶点构成的向量与三个边代表的向量（必须是一个顺序，都是逆时针，或都是顺时针）的叉积都大于0或者都小于0，则Leyni在三角形内。需要注意的是不能只考虑一种情况，例如只考虑>0的情况，而不考虑<0的情况，这样会WA。
复杂代码：
#include <stdio.h>
#define eps 1e-10
typedef struct{ //定义点
double x,y;
}Point;
typedef Point Vector; //定义向量
double Cross(Vector a,Vector b) //叉积
{
return a.x*b.y - a.y*b.x;
}
bool isn(Point a,Point b,Point c,Point p) //判断点p是否在三角形abc内
{
Vector ab,bc,ca; //创建向量
Vector ap,bp,cp;
ab.x = b.x - a.x;ab.y = b.y - a.y; //向量赋值
bc.x = c.x - b.x;bc.y = c.y - b.y;
ca.x = a.x - c.x;ca.y = a.y - c.y;
ap.x = p.x - a.x;ap.y = p.y - a.y;
bp.x = p.x - b.x;bp.y = p.y - b.y;
cp.x = p.x - c.x;cp.y = p.y - c.y; if( Cross(ab,ap)>eps && Cross(bc,bp)>eps && Cross(ca,cp)>eps ||
Cross(ab,ap)<eps && Cross(bc,bp)<eps && Cross(ca,cp)<eps) //核心代码。注意不能单考虑一种情况（>0 或 <0）
return true;
else
return false;
}
int main()
{
int x1,y1,x2,y2,x3,y3,xLeyni,yLeyni;
while(scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&xLeyni,&yLeyni)!=EOF){ //输入四对坐标
if( (xLeyni==x1 && yLeyni==y1) ||
(xLeyni==x2 && yLeyni==y2) ||
(xLeyni==x3 && yLeyni==y3) ){
printf("Die\n"); //如果Leyni正好在三角形顶点上，则直接死掉
continue;
}
Point a,b,c,p; //将输入的坐标赋给点
a.x = double(x1),a.y = double(y1);
b.x = double(x2),b.y = double(y2);
c.x = double(x3),c.y = double(y3);
p.x = double(xLeyni),p.y = double(yLeyni); if(isn(a,b,c,p)) //判断是否在三角形内
printf("Die\n");
else
printf("Live\n");
}
return ;
}
优化代码：
#include <stdio.h>
typedef struct { //定义点
double x,y;
}Point;
double Cross(Point a,Point b,Point c) //三点求叉积
{
return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}
int main()
{
Point a,b,c,p; //定义四点
while(scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&p.x,&p.y)!=EOF){ //输入四对坐标
if( (Cross(a,b,p)> && Cross(b,c,p)> && Cross(c,a,p)>) ||
(Cross(a,b,p)< && Cross(b,c,p)< && Cross(c,a,p)<) ) //判断点p是否在三角形abc内。注意不能只考虑一种情况(<0 或 >0)
printf("Die\n");
else
printf("Live\n");
}
return ;
}
Freecode : www.cnblogs.com/yym2013