Question

在线等，急求一道C语言的编程题！！！正确答案直接发20元微信红包

Answer 1

凸包问题。计算几何。

#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

算法描述里面也有。

Answer 2

排序，先按照x坐标排序，找出x最大、最小两点（左右最边点）。连接这两点，其他各点，按纵坐标分组，纵坐标在该线上方的归一组，该线下方的归一组。两组中的点，一组在下边，一组在上边。按横坐标，是相邻的点。这样点可以任意输。
上方的点，在左右邻居连线的上方为凸，下方非凸；下方的点，位于左右邻居连线的下方为凸，上方非凸。
判断内外：根据x值，找出该点左右相邻的下边、上边两点，y值如果位于上下个两点的连线之间（包括线上），就是在内部，否则在外部。

Answer 3

计算原理：
（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.