讨论 / 水到几何题
libin66 2015-09-02 06:29:48
点我顶贴 收藏 删除
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<string>

#include<vector>

#include <ctime>

#include<queue>

#include<set>

#include<map>

#include<stack>

#include<cmath>

#define mst(ss,b) memset((ss),(b),sizeof(ss))

#define maxn 0x3f3f3f3f

///#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

struct point {

double x,y;

point(double x=0,double y=0):x(x),y(y) {}

};

typedef point vec;

const double eps=1e-8;

const double pi=acos(-1.0);

bool cmp(point a,point b) {

if(fabs(a.x-b.x)<=eps) return a.y<b.y;

return a.x<b.x;

}

vec operator -(point a,point b) {

return vec(a.x-b.x,a.y-b.y);

}

vec operator +(point a,point b) {

return vec(a.x+b.x,a.y+b.y);

}

vec operator *(point a,double t) {

return vec(a.x*t,a.y*t);

}

vec operator /(point a,double t) {

return vec(a.x/t,a.y/t);

}

bool operator < (const point &a,const point &b) {

return a.y<b.y || (fabs(a.y-b.y)<=eps && a.x<b.x);

}

bool operator == (const point &a,const point &b) {

if(fabs(a.x-b.x)<=eps && fabs(a.y-b.y)<=eps)

return true;

return false;

}

int dcmp(double x) {

if(fabs(x)<=eps) return 0;

return x<0?-1:1;

}

double cross(vec a,vec b) {///叉积

return a.x*b.y-a.y*b.x;

}

double dot(vec a,vec b) {///点积

return a.x*b.x+a.y*b.y;

}

double disn(point a,point b) {

return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

/*两点之间的距离*/

}

double lentgh(vec a){///向量长度

return sqrt(dot(a,a));

}

bool onseg(point p,point a1,point a2){

return dcmp(cross(a1-p,a2-p))==0 && dcmp(dot(a1-p,a2-p))<0;

/*点在线段上 不包含端点(<=0)*/

}

int pointinpoly(point p,point *poly,int n){

int wn=0;

for(int i=0;i<n;i++){

if(onseg(p,poly[i],poly[(i+1)%n])) return -1;///点在边界上

int k=dcmp(cross(poly[(i+1)%n]-poly[i],p-poly[i]));

int d1=dcmp(poly[i].y-p.y);

int d2=dcmp(poly[(i+1)%n].y-p.y);

if(k>0 && d1<=0 && d2>0) wn++;

if(k<0 && d2<=0 && d1>0) wn--;

}

if(wn!=0) return 1;///内部

return 0;///外部

/*点在多边形内 p是点 poly[]是多边形

多边形的点必须是顺时针或者逆时针

n是点的个数

*/

}

void convexhull(point *s,int &n) {

sort(s,s+n,cmp);

int m=0;

point p[110];

for(int i=0; i<n; i++) {

while(m>1 && dcmp(cross(p[m-1]-p[m-2],s[i]-p[m-2]))<=0)

m--;

p[m++]=s[i];

}

int k=m;

for(int i=n-2; i>=0; i--) {

while(m>k && dcmp(cross(p[m-1]-p[m-2],s[i]-p[m-2]))<=0)

m--;

p[m++]=s[i];

}

m--;

n=m;

for(int i=0; i<n; i++) s[i]=p[i];

/*建立凸包*/

}

int n,m;

point s[110];

int main(){

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

for(int i=0;i<n;i++) scanf("%lf%lf",&s[i].x,&s[i].y);

convexhull(s,n);

for(int i=0;i<m;i++){

point t;

scanf("%lf%lf",&t.x,&t.y);

if(pointinpoly(t,s,n)) printf("1\n");

else printf("0\n");

}

return 0;

}

查看更多回复
提交回复