我看的这里:http://www.cnblogs.com/ka200812/archive/2012/01/20/2328316.html
然后整理一下当做模版。0换成eps,会wa,应该要写成精度特判把。
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
#define eps 1e-8
#define N 110
struct point
{
double x,y;
}p[N],temp[N],pre[N];
int n,m;
double a,b,c;
void getline(point x,point y)
{
a = y.y - x.y;
b = x.x - y.x;
c = y.x * x.y - x.x * y.y;
}
point intersect(point x,point y) //获取直线ax+by+c==0 和点x和y所连直线的交点
{
double u = fabs(a*x.x+b*x.y+c);
double v = fabs(a*y.x+b*y.y+c);
point ans;
ans.x = (x.x*v+y.x*u)/(u+v);
ans.y = (x.y*v+y.y*u)/(u+v);
return ans;
}
void cut()
{
int num = ,i;
for(i = ;i <= m;i ++)
{
if(a*p[i].x + b*p[i].y + c >= )
{
temp[++num] = p[i];
}
else
{
if(a*p[i-].x + b*p[i-].y + c > )
temp[++num] = intersect(p[i],p[i-]);
if(a*p[i+].x + b*p[i+].y + c > )
temp[++num] = intersect(p[i],p[i+]);
}
}
for(i = ;i <= num;i ++)
p[i] = temp[i];
p[] = p[num];
p[num+] = p[];
m = num;
}
void fun()
{
int i;
m = n;
for(i = ;i <= n;i ++)
{
getline(pre[i],pre[i+]);
cut();
}
}
int main()
{
int i,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i = ;i <= n;i ++)
{
scanf("%lf%lf",&pre[i].x,&pre[i].y);
p[i] = pre[i];
}
pre[n+] = pre[];
p[n+] = p[];
p[] = p[n];
fun();
if(m)
printf("YES\n");
else
printf("NO\n");
}
return ;
}