讨论 / 刚学的Jarvis步进法,来做这个题简直so easy,代码有点长,见谅
沧海一声喵 2018-01-26 06:18:15
点我顶贴 收藏 删除
#include <cstdio>

#include <vector>

#include <cmath>

using namespace std;

int main(){

int n,i,f,p,m,flag;

double a,d,a1,d1,x0,y0,x1,y1,x2,y2,x[101],y[101],dx[101],dy[101];

vector<int> v;

scanf("%d%d",&n,&m);

for(i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);

for(i=1;i<=m;i++) scanf("%lf%lf",&dx[i],&dy[i]);

for(f=1,i=2;i<=n;i++)

if(y[i]<y[f]||(y[i]==y[f]&&x[i]<x[f])) f=i;

v.push_back(f);

for(a=0,d=1000000.0,i=1;i<=n;i++){

if(i!=f){

d1=sqrt((x[i]-x[f])*(x[i]-x[f])+(y[i]-y[f])*(y[i]-y[f]));

a1=(x[i]-x[f])/d1;

if(a1>a||(a1==a&&d1<d)){

a=a1;p=i;d=d1;}}}

v.push_back(p);

while(1){

x0=x[v[v.size()-2]];y0=y[v[v.size()-2]];

x1=x[v[v.size()-1]];y1=y[v[v.size()-1]];

x1-=x0;y1-=y0;

for(a=0,d=10000000.0,f=0,i=1;i<=n;i++){

if(i!=v[v.size()-2]&&i!=v[v.size()-1]){

x2=x[i];y2=y[i];

x2=x2-x1-x0;y2=y2-y1-y0;

d1=sqrt(x2*x2+y2*y2);

a1=(x1*x2+y1*y2)/(d1*sqrt(x1*x1+y1*y1));

if(a1>a||(a1==a&&d1<d)){

a=a1;f=i;d=d1;}}}

if(f!=v[0]) v.push_back(f);

else break;}

for(i=1;i<=m;i++){

flag=1;

for(p=0;p<v.size()-1;p++){

x0=dx[i]-x[v[p]];y0=dy[i]-y[v[p]];

x2=x[v[p+1]]-x[v[p]];y2=y[v[p+1]]-y[v[p]];

if(x0*y2>x2*y0){

flag=0;break;}}

x0=dx[i]-x[v.back()];y0=dy[i]-y[v.back()];

x2=x[v[0]]-x[v.back()];y2=y[v[0]]-y[v.back()];

if(x0*y2>x2*y0) flag=0;

if(flag) printf("1\n");

else printf("0\n");}

return 0;}

查看更多回复
提交回复