凸包问题。计算几何。
#include<stdio.h>#include<string.h>
struct node
{
long long x,y;
}a[100005],b[100005];
long long mul(node p1,node p2,node p3)
{
return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
int main()
{
int n,m,i,low,high,mid,flag;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%lld%lld",&a[i].x,&a[i].y);
scanf("%d",&m);
for(i=0;i<m;i++)
scanf("%lld%lld",&b[i].x,&b[i].y);
flag=0;
for(i=0;i<m;i++)
{
if(mul(a[0],a[1],b[i])>=0||mul(a[0],a[n-1],b[i])<=0)
{
flag=1;
goto loop;
}
low=2; high=n-1;
while(low<high)
{
mid=(low+high)>>1;
if(mul(a[0],a[mid],b[i])>0)
high=mid;
else low=mid+1;
}
if(mul(a[low],a[low-1],b[i])<=0)
{
flag=1;
goto loop;
}
}
loop: if(flag)
printf("NO\n");
else printf("YES\n");
}
return 0;
}
转自http://www.cnblogs.com/dream-wind/archive/2012/05/23/2514694.html
算法描述里面也有。
上方的点，在左右邻居连线的上方为凸，下方非凸；下方的点，位于左右邻居连线的下方为凸，上方非凸。
判断内外：根据x值，找出该点左右相邻的下边、上边两点，y值如果位于上下个两点的连线之间（包括线上），就是在内部，否则在外部。
（1）是否为凸多边形：前三个点计算三角形（封闭线的面积，用积分方式计算），以后每加一个点面积均应增加或至少相等。
（2）最后一个点是否在凸多边形内：同上方式计算加上这个点的多边形的面积，相等或减少表示在内 ！追答
已用pascal语言实现！代码较长，手机上无法提交！需要的话请给出邮箱。
{2
5;-1,0;0,1;1,0;-1,0;0,0
5;0,-1;1,0;0,1;0,-1;2,2
}
var
x,y,x1,y1,x2,y2,x3,y3,x4,y4:array[1..100] of integer;
xn,yn:integer;
k1,k2,k3,k4:integer;
r1,r2,r3,r4:array[1..100] of real;
t:integer; tr:real;
sx,sy:integer;
ax,ay:real;
m,n:integer;
s:string;
stx,sty:string[6];
st:string[12];
i,j,k,code,p,q:integer;
f:text;
function area(n:integer):real;
{利用积分方法求面积的函数}
var
i:integer;
t:real;
begin
t:=0;
for i:=1 to n-1 do t:=t+0.5*(y[i+1]+y[i])*(x[i+1]-x[i]);
t:=t+0.5*(y[1]+y[n])*(x[1]-x[n]);
area:=abs(t);
end;
begin
assign(f,'凸多边形.in'); reset(f);
readln(f,m);
for i:=1 to m do begin
{以下读取每一行并将其分解出点数n以及n个点的坐标}
readln(f,s);
k:=pos(';',s);
val(copy(s,1,k-1),n,code);
s:=copy(s,k+1,length(s));
for j:=1 to n-1 do begin
k:=pos(';',s);
st:=copy(s,1,k-1); s:=copy(s,k+1,length(s));
k:=pos(',',st);
stx:=copy(st,1,k-1);
sty:=copy(st,k+1,length(st));
val(stx,x[j],code);
val(sty,y[j],code);
end;
st:=s;
k:=pos(',',st);
stx:=copy(st,1,k-1);
sty:=copy(st,k+1,length(st));
val(stx,x[n],code);
val(sty,y[n],code);
xn:=x[n]; yn:=y[n];
{以下将坐标点分到四个象限}
{以所有坐标点的坐标的算术平均值对应的点作为相对坐标系的原点}
sx:=0; sy:=0;
for j:=1 to n do begin
sx:=sx+x[j]; sy:=sy+y[j];
end;
ax:=sx/n; ay:=sy/n;
k1:=0;
for j:=1 to n do
if (x[j]-ax>0)and(y[j]-ay>=0) then begin
inc(k1);
x1[k1]:=x[j]; y1[k1]:=y[j];
r1[k1]:=(y[j]-ay)/(x[j]-ax);
end;
k2:=0;
for j:=1 to n do
if (x[j]-ax0) then begin
inc(k2);
x2[k2]:=x[j]; y2[k2]:=y[j];
if x[j]-ax=0 then r2[k2]:=-1e15 else r2[k2]:=(y[j]-ay)/(x[j]-ax);
end;
k3:=0;
for j:=1 to n do
if (
以下重新发：
var
x,y,x1,y1,x2,y2,x3,y3,x4,y4:array[1..100] of integer;
xn,yn:integer;
k1,k2,k3,k4:integer;
r1,r2,r3,r4:array[1..100] of real;
t:integer; tr:real;
sx,sy:integer;
ax,ay:real;
m,n:integer;
s:string;
stx,sty:string[6];
st:string[12];
i,j,k,code,p,q:integer;
f:text;
function area(n:integer):real;
{利用积分方法求面积的函数}
var
i:integer;
t:real;
begin
t:=0;
for i:=1 to n-1 do t:=t+0.5*(y[i+1]+y[i])*(x[i+1]-x[i]);
t:=t+0.5*(y[1]+y[n])*(x[1]-x[n]);
area:=abs(t);
end;
begin
assign(f,'凸多边形.in'); reset(f);
readln(f,m);
for i:=1 to m do begin
{以下读取每一行并将其分解出点数n以及n个点的坐标}
readln(f,s);
k:=pos(';',s);
val(copy(s,1,k-1),n,code);
s:=copy(s,k+1,length(s));
for j:=1 to n-1 do begin
k:=pos(';',s);
st:=copy(s,1,k-1); s:=copy(s,k+1,length(s));
k:=pos(',',st);
stx:=copy(st,1,k-1);
sty:=copy(st,k+1,length(st));
val(stx,x[j],code);
val(sty,y[j],code);
end;
st:=s;
k:=pos(',',st);
stx:=copy(st,1,k-1);
sty:=copy(st,k+1,length(st));
val(stx,x[n],code);
val(sty,y[n],code);
xn:=x[n]; yn:=y[n];
{以下将坐标点分到四个象限}
{以所有坐标点的坐标的算术平均值对应的点作为相对坐标系的原点}
sx:=0; sy:=0;
for j:=1 to n do begin
sx:=sx+x[j]; sy:=sy+y[j];
end;
ax:=sx/n; ay:=sy/n;
k1:=0;
for j:=1 to n do
if (x[j]-ax>0)and(y[j]-ay>=0) then begin
inc(k1);
x1[k1]:=x[j]; y1[k1]:=y[j];
r1[k1]:=(y[j]-ay)/(x[j]-ax);
end;
k2:=0;
for j:=1 to n do
if (x[j]-ax0) then begin
inc(k2);
x2[k2]:=x[j]; y2[k2]:=y[j];
if x[j]-ax=0 then r2[k2]:=-1e15 else r2[k2]:=(y[j]-ay)/(x[j]-ax);
end;
k3:=0;
for j:=1 to n do
if (x[j]-ax=0)and(y[j]-ay1 then
for p:=1 to k1-1 do for q:=p+1 to k1 do
if r1[p]>r1[q] then begin
tr:=r1[p]; r1[p]:=r1[q]; r1[q]:=tr;
t:=x1[p]; x1[p]:=x1[q]; x1[q]:=t;
t:=y1[p]; y1[p]:=y1[q]; y1[q]:=t;
end;
if k2>1 then
for p:=1 to k2-1 do for q:=p+1 to k2 do
if r2[p]>r2[q] then begin
tr:=r2[p]; r2[p]:=r2[q]; r2[q]:=tr;
t:=x2[p]; x2[p]:=x1[q]; x2[q]:=t;
t:=y2[p]; y2[p]:=y1[q]; y2[q]:=t;
end;
if k3>1 then
for p:=1 to k3-1 do for q:=p+1 to k3 do
if r3[p]>r3[q] then begin
tr:=r3[p]; r3[p]:=r3[q]; r3[q]:=tr;
t:=x3[p]; x3[p]:=x3[q]; x3[q]:=t;
t:=y3[p]; y3[p]:=y3[q]; y3[q]:=t;
end;
if k4>1 then
for p:=1 to k4-1 do for q:=p+1 to k4 do
if r4[p]>r4[q] then begin
tr:=r4[p]; r4[p]:=r4[q]; r4[q]:=tr;
t:=x4[p]; x4[p]:=x4[q]; x4[q]:=t;
t:=y4[
{以下合并生成新的顺序的数组x、y}
for j:=1 to k1 do begin x[j]:=x1[j]; y[j]:=y1[j]; end;
for j:=k1+1 to k1+k2 do begin x[j]:=x2[j-k1]; y[j]:=y2[j-k1]; end;
for j:=k1+k2+1 to k1+k2+k3 do begin x[j]:=x3[j-k1-k2]; y[j]:=y3[j-k1-k2]; end;
for j:=k1+k2+k3+1 to k1+k2+k3+k4 do begin x[j]:=x4[j-k1-k2-k3]; y[j]:=y4[j-k1-k2-k3]; end;
{以下确定第n点在排序后的坐标点中的位置}
for j:=1 to n do if (x[j]=xn)and(y[j]=yn) then begin k:=j; break; end;
x1:=x; y1:=y;
{以下将第n点调整到队列的末尾}
p:=0;
for j:=k+1 to n do begin inc(p); x[p]:=x1[j]; y[p]:=y1[j]; end;
for j:=1 to k-1 do begin inc(p); x[p]:=x1[j]; y[p]:=y1[j]; end;
x[n]:=xn; y[n]:=yn;
{以下判断是否在凸多边形内}
if area(n)<=area(n-1) then writeln('1') else writeln('0');
end;
close(f);
end.